test/aoj/3148.test.cpp

View this file on GitHub
Last update: 2020-10-27 16:41:24+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3148

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3148"

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../tools/chminmax.cpp"
#include "../../tools/drop.cpp"
#include "../../tree/rerooting.cpp"
#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  using ll = long long;

  struct T{
    ll a,b,c;
    T(ll a,ll b,ll c):a(a),b(b),c(c){}
  };

  const ll INF = 1e9;
  auto fold=[&](T x,T y){
    vector<ll> vs({x.a,x.b,x.c,y.a,y.b,y.c});
    sort(vs.rbegin(),vs.rend());
    return T(vs[0],vs[1],vs[2]);
  };
  auto lift=[&](T x,ll y){
    chmax(x.a,0);
    x.a+=y;
    x.b=-INF;
    x.c=-INF;
    return x;
  };

  int n;
  cin>>n;
  if(n==1) drop(1);

  ReRooting<T, ll> G(n,fold,lift,T(-INF,-INF,-INF));
  for(int i=1;i<n;i++){
    int u,v;
    cin>>u>>v;
    u--;v--;
    G.add_edge(u,v,1);
  }
  auto res=G.build();

  string ans(n+1,'1');

  for(int i=0;i<n;i++){
    if(G.G[i].size()<3) continue;
    T v=res[i];
    ans[v.a+min({v.a-1,v.b,v.c})]='0';
  }

  for(int i=n-1;i>=0;i--)
    if(ans[i+1]=='0') ans[i]='0';

  ans[1]='1';
  ans[2]='1';
  cout<<ans.substr(1)<<endl;
  return 0;
}

#line 1 "test/aoj/3148.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3148"

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "tools/chminmax.cpp"

#line 3 "tools/chminmax.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "tools/drop.cpp"

#line 3 "tools/drop.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 1 "tree/rerooting.cpp"

#line 3 "tree/rerooting.cpp"
using namespace std;
#endif

//BEGIN CUT HERE
template<typename T, typename Edge>
struct ReRooting{
  struct Node{
    int to,rev;
    Edge data;
    Node(int to,Edge data):to(to),data(data){}
    bool operator<(const Node &v)const{return to<v.to;};
  };

  using Fold = function<T(T, T)>;
  using Lift = function<T(T, Edge)>;

  vector< vector<Node> > G;
  vector< vector<T> > ld,rd;
  vector<int> lp,rp;

  const Fold fold;
  const Lift lift;
  const T id;

  ReRooting(int n,const Fold fold,const Lift lift,const T id):
    G(n),ld(n),rd(n),lp(n),rp(n),fold(fold),lift(lift),id(id){}

  void add_edge(int u,int v,Edge d,Edge e){
    G[u].emplace_back(v,d);
    G[v].emplace_back(u,e);
  }

  void add_edge(int u,int v,Edge d){add_edge(u,v,d,d);}

  // k: idx for edge (not vertex)
  T dfs(int v,int k){
    while(lp[v]!=k and lp[v]<(int)G[v].size()){
      auto &e=G[v][lp[v]];
      ld[v][lp[v]+1]=fold(ld[v][lp[v]],lift(dfs(e.to,e.rev),e.data));
      lp[v]++;
    }
    while(rp[v]!=k and rp[v]>=0){
      auto &e=G[v][rp[v]];
      rd[v][rp[v]]=fold(rd[v][rp[v]+1],lift(dfs(e.to,e.rev),e.data));
      rp[v]--;
    }
    if(k<0) return rd[v][0];
    return fold(ld[v][k],rd[v][k+1]);
  }

  int search(vector<Node> &vs,int idx){
    return lower_bound(vs.begin(),vs.end(),Node(idx,vs[0].data))-vs.begin();
  }

  vector<T> build(){
    int n=G.size();
    for(int i=0;i<n;i++){
      sort(G[i].begin(),G[i].end());
      ld[i].assign((int)G[i].size()+1,id);
      rd[i].assign((int)G[i].size()+1,id);
      lp[i]=0;
      rp[i]=(int)G[i].size()-1;
    }

    for(int i=0;i<n;i++)
      for(Node &t:G[i])
        t.rev=search(G[t.to],i);

    vector<T> res;
    for(int i=0;i<n;i++)
      res.emplace_back(dfs(i,-1));

    return res;
  }

  // p: idx for vertex
  T subtree(int v,int p){
    int k=search(G[p],v);
    assert(k<(int)G[p].size() and G[p][k].to==v);
    return lift(dfs(v,G[p][k].rev),G[p][k].data);
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 10 "test/aoj/3148.test.cpp"
#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  using ll = long long;

  struct T{
    ll a,b,c;
    T(ll a,ll b,ll c):a(a),b(b),c(c){}
  };

  const ll INF = 1e9;
  auto fold=[&](T x,T y){
    vector<ll> vs({x.a,x.b,x.c,y.a,y.b,y.c});
    sort(vs.rbegin(),vs.rend());
    return T(vs[0],vs[1],vs[2]);
  };
  auto lift=[&](T x,ll y){
    chmax(x.a,0);
    x.a+=y;
    x.b=-INF;
    x.c=-INF;
    return x;
  };

  int n;
  cin>>n;
  if(n==1) drop(1);

  ReRooting<T, ll> G(n,fold,lift,T(-INF,-INF,-INF));
  for(int i=1;i<n;i++){
    int u,v;
    cin>>u>>v;
    u--;v--;
    G.add_edge(u,v,1);
  }
  auto res=G.build();

  string ans(n+1,'1');

  for(int i=0;i<n;i++){
    if(G.G[i].size()<3) continue;
    T v=res[i];
    ans[v.a+min({v.a-1,v.b,v.c})]='0';
  }

  for(int i=n-1;i>=0;i--)
    if(ans[i+1]=='0') ans[i]='0';

  ans[1]='1';
  ans[2]='1';
  cout<<ans.substr(1)<<endl;
  return 0;
}