Submission #76571

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
76571	2018-09-14T20:29:23 Z	born2rule	Werewolf (IOI18_werewolf)	C++14	100 / 100	1971 ms	218452 KB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const int N=200005;
/*vi v[N];
bool vis[N];
void dfs(int u,int l,int r,vi &tmp,int type=0)
{
  if(type==0 && u<l) return;
  if(type==1 && u>r) return;
  vis[u]=true;
  tmp.pb(u);
  for(int v1:v[u])
    {
      if(vis[v1]) continue;
      dfs(v1,l,r,tmp,type);
    }
}
vi subtask12(int n,vi S,vi E,vi L,vi R)
{
  int q=sz(S);
  vi ans(q,0);
  rep(i,0,q)
    {
      int x=S[i],y=E[i],l=L[i],r=R[i]; x++,y++,l++,r++;
      if(x<l || y>r)
	continue;
      vi tmp1,tmp2;
      rep(j,1,n+1) vis[j]=false;
      dfs(x,l,r,tmp1);
      rep(j,1,n+1) vis[j]=false;
      dfs(y,l,r,tmp2,1);
      sort(all(tmp1)); sort(all(tmp2));
      bool ok=false;
      for(int x:tmp1)
	{
	  int ind=lower_bound(all(tmp2),x)-tmp2.begin();
	  if(ind!=sz(tmp2) && tmp2[ind]==x) ok=true;
	}
      if(ok) ans[i]=1;
    }
  return ans;
}*/
const int L=3*N,LN=20;
vi ad[N];
int par[L],val[2][L],val2[L],p[2][LN][L];
vi v[2][L];//edges for 1st tree and 2nd tree
int st[2][L],en[2][L],child[2][L],timer[]={1,1};
int rev[2][L],bit[L];
vector<ii> queries[L];
int finda(int u)
{
  if(par[u]==u) return u;
  return par[u]=finda(par[u]);
}
int cnt;
void dfs(int u,int type=0,int pa=0)
{
  p[type][0][u]=pa;
  rev[type][timer[type]]=u;
  st[type][u]=timer[type]++;
  child[type][u]=1;
  for(int v1:v[type][u])
    dfs(v1,type,u),child[type][u]+=child[type][v1];
  en[type][u]=timer[type];
}
void update(int i,int val)
{
  while(i<L)
    {
      bit[i]+=val;
      i+=(i&(-i));
    }
}
int query(int i)
{
  int ans=0;
  while(i)
    {
      ans+=bit[i];
      i-=(i&(-i));
    }
  return ans;
}
void calcdfs(int u,int type,bool keep,int n,vi &ans)
{
  int mx=-1,bigchild=-1;
  for(int v1:v[type][u])
    {
      if(child[type][v1]>mx)
	mx=child[type][v1],bigchild=v1;
    }
  for(int v1:v[type][u])
    if(v1!=bigchild)
      calcdfs(v1,type,0,n,ans);
  if(bigchild!=-1)
    calcdfs(bigchild,type,1,n,ans);
  for(int v1:v[type][u])
    {
      if(v1==bigchild) continue;
      rep(i,st[type][v1],en[type][v1])
	{
	  int x=rev[type][i];
	  if(x>=1 && x<=n)
	    update(st[1-type][x],1);
	}
    }
  if(u>=1 && u<=n) update(st[1-type][u],1);
  for(auto it:queries[u])
    {
      int tmp=query(en[1-type][it.fi]-1)-query(st[1-type][it.fi]-1);
      if(tmp) ans[it.se]=1;
    }
  if(!keep)
    {
      rep(i,st[type][u],en[type][u])
	{
	  int x=rev[type][i];
	  if(x>=1 && x<=n)
	    update(st[1-type][x],-1);
	}
    }
}
vi solve(int n,vi X,vi Y,vi S,vi E,vi L,vi R)
{
  //let U be set of reachable nodes from s which are at >R, we need to represent it as a subtree, similarly for nodes<L
  cnt=n;
  rep(i,0,sz(X)) X[i]++,Y[i]++;
  rep(i,0,sz(X))
    ad[min(X[i],Y[i])].pb(max(X[i],Y[i]));
  rep(i,1,n+1) par[i]=i,val[0][i]=n;
  repv(i,1,n)//add edges in reverse order
    {
      for(int v1:ad[i])
	{
	  int x=finda(i),y=finda(v1);
	  if(x==y) continue;
	  cnt++; par[x]=par[y]=par[cnt]=cnt;//make a new node
	  v[0][cnt].pb(x); v[0][cnt].pb(y);
	  //trace(cnt,i,v1,x,y,"burrah");
	  val[0][cnt]=i;//index till which edges are added
	}
    }
  int root[2];
  root[0]=cnt;
  rep(i,1,n+1) ad[i].clear(),par[i]=i,val[1][i]=1;
  rep(i,0,sz(X))
    ad[max(X[i],Y[i])].pb(min(X[i],Y[i]));
  rep(i,2,n+1)//add edges in reverse order
    {
      for(int v1:ad[i])
	{
	  int x=finda(i),y=finda(v1);
	  if(x==y) continue;
	  cnt++; par[x]=par[y]=par[cnt]=cnt;//make a new node
	  v[1][cnt].pb(x); v[1][cnt].pb(y);
	  //trace(cnt,i,v1,x,y);
	  val[1][cnt]=i;//index till which edges are added
	}
    }
  root[1]=cnt;
  //make euler tour of both trees
  rep(i,0,2) dfs(root[i],i,root[i]);
  rep(k,0,2)
    rep(i,1,LN)
    rep(j,1,cnt+1)
    p[k][i][j]=p[k][i-1][p[k][i-1][j]];
  vi ans(sz(S),0);
  rep(i,0,sz(S))
    {
      int x=S[i],y=E[i],l=L[i],r=R[i]; x++,y++,l++,r++;
      if(x<l || y>r)
	continue;
      //find subtree corr. to x s.t. only nodes >=l are reachable
      int curr1=x;
      repv(j,0,LN)
	{
	  //if(i==0 && j<=6)
	  //trace(val[0][p[0][j][curr1]],p[0][j][curr1],j);
	  if(val[0][p[0][j][curr1]]>=l)
	    curr1=p[0][j][curr1];
	}
      int curr2=y;
      repv(j,0,LN)
	if(val[1][p[1][j][curr2]]<=r)
	  curr2=p[1][j][curr2];
      //trace(x,y,l,r,curr1,curr2);
      //now check if subtrees of curr1 and curr2 intersect
      queries[curr1].pb(mp(curr2,i));
    }
  calcdfs(root[0],0,0,n,ans);
  return ans;
}
vi check_validity(int n,vi X,vi Y,vi S,vi E,vi L,vi R)
{
  int q=sz(S);
  /*rep(i,0,sz(X))
    {
      X[i]++; Y[i]++;
      v[X[i]].pb(Y[i]);
      v[Y[i]].pb(X[i]);
    }
  if(n<=3000 && q<=3000)
    return subtask12(n,S,E,L,R);*/
  return solve(n,X,Y,S,E,L,R);
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:233:7: warning: unused variable 'q' [-Wunused-variable]
   int q=sz(S);
       ^

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	47864 KB	Output is correct
2	Correct	42 ms	47864 KB	Output is correct
3	Correct	43 ms	47864 KB	Output is correct
4	Correct	43 ms	48000 KB	Output is correct
5	Correct	41 ms	48092 KB	Output is correct
6	Correct	42 ms	48092 KB	Output is correct
7	Correct	43 ms	48092 KB	Output is correct
8	Correct	42 ms	48092 KB	Output is correct
9	Correct	45 ms	48092 KB	Output is correct

Subtask #2

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	47864 KB	Output is correct
2	Correct	42 ms	47864 KB	Output is correct
3	Correct	43 ms	47864 KB	Output is correct
4	Correct	43 ms	48000 KB	Output is correct
5	Correct	41 ms	48092 KB	Output is correct
6	Correct	42 ms	48092 KB	Output is correct
7	Correct	43 ms	48092 KB	Output is correct
8	Correct	42 ms	48092 KB	Output is correct
9	Correct	45 ms	48092 KB	Output is correct
10	Correct	55 ms	50352 KB	Output is correct
11	Correct	53 ms	50352 KB	Output is correct
12	Correct	53 ms	50352 KB	Output is correct
13	Correct	54 ms	50380 KB	Output is correct
14	Correct	53 ms	50508 KB	Output is correct
15	Correct	52 ms	50508 KB	Output is correct

Subtask #3

34.0 / 34.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1801 ms	196956 KB	Output is correct
2	Correct	1305 ms	203736 KB	Output is correct
3	Correct	1253 ms	203736 KB	Output is correct
4	Correct	1348 ms	203736 KB	Output is correct
5	Correct	1340 ms	203736 KB	Output is correct
6	Correct	1549 ms	203736 KB	Output is correct
7	Correct	1452 ms	203736 KB	Output is correct
8	Correct	1153 ms	203756 KB	Output is correct
9	Correct	872 ms	203756 KB	Output is correct
10	Correct	774 ms	203756 KB	Output is correct
11	Correct	882 ms	203756 KB	Output is correct
12	Correct	942 ms	203756 KB	Output is correct
13	Correct	1440 ms	207904 KB	Output is correct
14	Correct	1346 ms	207996 KB	Output is correct
15	Correct	1403 ms	207996 KB	Output is correct
16	Correct	1467 ms	208020 KB	Output is correct
17	Correct	1506 ms	208020 KB	Output is correct

Subtask #4

51.0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	47864 KB	Output is correct
2	Correct	42 ms	47864 KB	Output is correct
3	Correct	43 ms	47864 KB	Output is correct
4	Correct	43 ms	48000 KB	Output is correct
5	Correct	41 ms	48092 KB	Output is correct
6	Correct	42 ms	48092 KB	Output is correct
7	Correct	43 ms	48092 KB	Output is correct
8	Correct	42 ms	48092 KB	Output is correct
9	Correct	45 ms	48092 KB	Output is correct
10	Correct	55 ms	50352 KB	Output is correct
11	Correct	53 ms	50352 KB	Output is correct
12	Correct	53 ms	50352 KB	Output is correct
13	Correct	54 ms	50380 KB	Output is correct
14	Correct	53 ms	50508 KB	Output is correct
15	Correct	52 ms	50508 KB	Output is correct
16	Correct	1801 ms	196956 KB	Output is correct
17	Correct	1305 ms	203736 KB	Output is correct
18	Correct	1253 ms	203736 KB	Output is correct
19	Correct	1348 ms	203736 KB	Output is correct
20	Correct	1340 ms	203736 KB	Output is correct
21	Correct	1549 ms	203736 KB	Output is correct
22	Correct	1452 ms	203736 KB	Output is correct
23	Correct	1153 ms	203756 KB	Output is correct
24	Correct	872 ms	203756 KB	Output is correct
25	Correct	774 ms	203756 KB	Output is correct
26	Correct	882 ms	203756 KB	Output is correct
27	Correct	942 ms	203756 KB	Output is correct
28	Correct	1440 ms	207904 KB	Output is correct
29	Correct	1346 ms	207996 KB	Output is correct
30	Correct	1403 ms	207996 KB	Output is correct
31	Correct	1467 ms	208020 KB	Output is correct
32	Correct	1506 ms	208020 KB	Output is correct
33	Correct	1737 ms	208020 KB	Output is correct
34	Correct	438 ms	208020 KB	Output is correct
35	Correct	1684 ms	208020 KB	Output is correct
36	Correct	1697 ms	208020 KB	Output is correct
37	Correct	1804 ms	208020 KB	Output is correct
38	Correct	1971 ms	208020 KB	Output is correct
39	Correct	1860 ms	212916 KB	Output is correct
40	Correct	1519 ms	212916 KB	Output is correct
41	Correct	1012 ms	212916 KB	Output is correct
42	Correct	888 ms	212916 KB	Output is correct
43	Correct	1492 ms	212916 KB	Output is correct
44	Correct	1381 ms	212916 KB	Output is correct
45	Correct	1041 ms	212916 KB	Output is correct
46	Correct	1092 ms	212916 KB	Output is correct
47	Correct	1417 ms	212916 KB	Output is correct
48	Correct	1444 ms	216448 KB	Output is correct
49	Correct	1434 ms	218452 KB	Output is correct
50	Correct	1349 ms	218452 KB	Output is correct
51	Correct	1391 ms	218452 KB	Output is correct
52	Correct	1176 ms	218452 KB	Output is correct