Submission #118077

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
118077	2019-06-18T06:43:55 Z	kig9981	Cats or Dogs (JOI18_catdog)	C++17	Compilation error	0 ms	0 KB

catdog

#include <bits/stdc++.h>
#include "catdog.h"

const int SZ=1<<17;
vector<int> adj[100000];
int node_cnt, depth[100000], parent[100000], W[100000], num[100000], num_rev[100000], hld[100000], V[100000], ans;
pair<int,int> tree[2*SZ], itree[2*SZ];

void set_tree(int n, int v)
{
	for(itree[n+=SZ].first=v;n>>=1;) itree[n]=max(itree[2*n],itree[2*n+1]);
}

pair<int,int> get_max(int s, int e)
{
	pair<int,int> ret;
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) ret=max(ret,itree[s++]);
		if(~e&1) ret=max(ret,itree[e--]);
	}
	return ret;
}

void add_tree(int s, int e, int v1, int v2)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) {
			tree[s].first+=v1;
			tree[s++].second+=v2;
		}
		if(~e&1) {
			tree[e].first+=v1;
			tree[e--].second+=v2;
		}
	}
}

pair<int,int> get_value(int n)
{
	pair<int,int> ret;
	for(ret=tree[n+=SZ];n>>=1;) {
		ret.first+=tree[n].first;
		ret.second+=tree[n].second;
	}
	return ret;
}

int dfs(int c)
{
	W[c]=1;
	for(auto n: adj[c]) if(W[n]==0) {
		parent[n]=c;
		depth[n]=depth[c]+1;
		W[c]+=dfs(n);
	}
	return W[c];
}

void dfs2(int c)
{
	num[c]=node_cnt++;
	num_rev[num[c]]=c;
	for(auto n: adj[c]) if(parent[n]==c && 2*W[n]>=W[c]) {
		hld[n]=hld[c];
		dfs2(n);
	}
	for(auto n: adj[c]) if(parent[n]==c && 2*W[n]<W[c]) {
		hld[n]=n;
		dfs2(n);
	}
}

void initialize(int N, vector<int> A, vector<int> B)
{
	itree[N-1].second=N-1; parent[0]=-1;
	for(int i=0;i<N-1;i++) {
		adj[--A[i]].push_back(--B[i]);
		adj[B[i]].push_back(A[i]);
		itree[i].second=i;
	}
	dfs(0); dfs2(0);
	for(int i=SZ-1;i;i--) itree[i]=max(itree[2*i],itree[2*i+1]);
}

int query(int a)
{
	while(a>=0) {
		auto temp=get_max(num[hld[a]],num[a]);
		if(temp.first) {
			int s=hld[a], e=a;
			while(s<=e) {
				int m=(s+e)>>1;
				temp=get_max(num[m],num[a]);
				if(temp.first) s=m+1;
				else e=m-1;
			}
			return temp.second;
		}
		a=parent[hld[a]];
	}
	return 0;
}

void update(int a, int b, int v1, int v2)
{
	if(b==-1) return;
	while(hld[a]!=hld[b]) {
		add_tree(num[hld[b]],num[b],v1,v2);
		b=parent[hld[b]];
	}
	add_tree(num[a],num[b],v1,v2);
}

int cat(int c)
{
	int idx=num[--c], pidx=query(c);
	auto[v1,v2]=get_value(idx);
	auto[pv1,pv2]=get_value(pidx);
	if(pidx || V[pidx]) {
		if(V[pidx]==1) ans-=pv2;
		else if(V[pidx]==2) ans-=pv1-1;
	}
	else ans+=min(pv1+1-v1,pv2-v2)-min(pv1,pv2);
	V[idx]=1; set_tree(idx,1);
	ans+=v2;
	update(num_rev[pidx],parent[num_rev[idx]],1-v1,-v2);
	return ans;
}

int dog(int c)
{
	int idx=num[--c], pidx=query(c);
	auto[v1,v2]=get_value(idx);
	auto[pv1,pv2]=get_value(pidx);
	if(pidx || V[pidx]) {
		if(V[pidx]==1) ans-=pv2-1;
		else if(V[pidx]==2) ans-=pv1;
	}
	else ans+=min(pv1-v1,pv2+1-v2)-min(pv1,pv2);
	V[idx]=2; set_tree(idx,2);
	ans+=v1;
	update(num_rev[pidx],parent[num_rev[idx]],-v1,1-v2);
	return ans;
}

int neighbor(int c)
{
	int idx=num[--c], pidx=query(parent[c]);
	auto[v1,v2]=get_value(idx);
	auto[pv1,pv2]=get_value(pidx);
	if(pidx || V[pidx]) {
		if(V[pidx]==1) ans-=pv2-v2;
		else if(V[pidx]==2) ans-=pv1-v1;
	}
	else ans+=min(pv1+v1-(V[idx]==1),pv2+v2-(V[idx]==2))-min(pv1,pv2);
	if(V[idx]==1) ans-=v2;
	else if(V[idx]==2) ans-=v1;
	update(num_rev[pidx],parent[num_rev[idx]],v1-(V[idx]==1),v2-(V[idx]==2));
	V[idx]=0; set_tree(idx,0);
	return ans;
}

Compilation message

catdog.cpp:5:1: error: 'vector' does not name a type; did you mean 'wctob'?
 vector<int> adj[100000];
 ^~~~~~
 wctob
catdog.cpp:7:1: error: 'pair' does not name a type; did you mean 'wait'?
 pair<int,int> tree[2*SZ], itree[2*SZ];
 ^~~~
 wait
catdog.cpp: In function 'void set_tree(int, int)':
catdog.cpp:11:6: error: 'itree' was not declared in this scope
  for(itree[n+=SZ].first=v;n>>=1;) itree[n]=max(itree[2*n],itree[2*n+1]);
      ^~~~~
catdog.cpp:11:6: note: suggested alternative: 'cfree'
  for(itree[n+=SZ].first=v;n>>=1;) itree[n]=max(itree[2*n],itree[2*n+1]);
      ^~~~~
      cfree
catdog.cpp:11:44: error: 'max' was not declared in this scope
  for(itree[n+=SZ].first=v;n>>=1;) itree[n]=max(itree[2*n],itree[2*n+1]);
                                            ^~~
catdog.cpp:11:44: note: suggested alternative:
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from catdog.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3468:5: note:   'std::max'
     max(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
catdog.cpp: At global scope:
catdog.cpp:14:1: error: 'pair' does not name a type; did you mean 'wait'?
 pair<int,int> get_max(int s, int e)
 ^~~~
 wait
catdog.cpp: In function 'void add_tree(int, int, int, int)':
catdog.cpp:28:4: error: 'tree' was not declared in this scope
    tree[s].first+=v1;
    ^~~~
catdog.cpp:28:4: note: suggested alternative: 'free'
    tree[s].first+=v1;
    ^~~~
    free
catdog.cpp:32:4: error: 'tree' was not declared in this scope
    tree[e].first+=v1;
    ^~~~
catdog.cpp:32:4: note: suggested alternative: 'free'
    tree[e].first+=v1;
    ^~~~
    free
catdog.cpp: At global scope:
catdog.cpp:38:1: error: 'pair' does not name a type; did you mean 'wait'?
 pair<int,int> get_value(int n)
 ^~~~
 wait
catdog.cpp: In function 'int dfs(int)':
catdog.cpp:51:14: error: 'adj' was not declared in this scope
  for(auto n: adj[c]) if(W[n]==0) {
              ^~~
catdog.cpp: In function 'void dfs2(int)':
catdog.cpp:63:14: error: 'adj' was not declared in this scope
  for(auto n: adj[c]) if(parent[n]==c && 2*W[n]>=W[c]) {
              ^~~
catdog.cpp:67:14: error: 'adj' was not declared in this scope
  for(auto n: adj[c]) if(parent[n]==c && 2*W[n]<W[c]) {
              ^~~
catdog.cpp: At global scope:
catdog.cpp:73:24: error: 'vector' has not been declared
 void initialize(int N, vector<int> A, vector<int> B)
                        ^~~~~~
catdog.cpp:73:30: error: expected ',' or '...' before '<' token
 void initialize(int N, vector<int> A, vector<int> B)
                              ^
catdog.cpp: In function 'void initialize(int, int)':
catdog.cpp:75:2: error: 'itree' was not declared in this scope
  itree[N-1].second=N-1; parent[0]=-1;
  ^~~~~
catdog.cpp:75:2: note: suggested alternative: 'cfree'
  itree[N-1].second=N-1; parent[0]=-1;
  ^~~~~
  cfree
catdog.cpp:77:3: error: 'adj' was not declared in this scope
   adj[--A[i]].push_back(--B[i]);
   ^~~
catdog.cpp:77:9: error: 'A' was not declared in this scope
   adj[--A[i]].push_back(--B[i]);
         ^
catdog.cpp:77:27: error: 'B' was not declared in this scope
   adj[--A[i]].push_back(--B[i]);
                           ^
catdog.cpp:82:33: error: 'max' was not declared in this scope
  for(int i=SZ-1;i;i--) itree[i]=max(itree[2*i],itree[2*i+1]);
                                 ^~~
catdog.cpp:82:33: note: suggested alternative:
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from catdog.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3468:5: note:   'std::max'
     max(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
catdog.cpp: In function 'int query(int)':
catdog.cpp:88:13: error: 'get_max' was not declared in this scope
   auto temp=get_max(num[hld[a]],num[a]);
             ^~~~~~~
catdog.cpp:88:13: note: suggested alternative: 'getchar'
   auto temp=get_max(num[hld[a]],num[a]);
             ^~~~~~~
             getchar
catdog.cpp: In function 'int cat(int)':
catdog.cpp:117:14: error: 'get_value' was not declared in this scope
  auto[v1,v2]=get_value(idx);
              ^~~~~~~~~
catdog.cpp:117:14: note: suggested alternative: 'si_value'
  auto[v1,v2]=get_value(idx);
              ^~~~~~~~~
              si_value
catdog.cpp:123:12: error: 'min' was not declared in this scope
  else ans+=min(pv1+1-v1,pv2-v2)-min(pv1,pv2);
            ^~~
catdog.cpp:123:12: note: suggested alternative:
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from catdog.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   'std::min'
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
catdog.cpp: In function 'int dog(int)':
catdog.cpp:133:14: error: 'get_value' was not declared in this scope
  auto[v1,v2]=get_value(idx);
              ^~~~~~~~~
catdog.cpp:133:14: note: suggested alternative: 'si_value'
  auto[v1,v2]=get_value(idx);
              ^~~~~~~~~
              si_value
catdog.cpp:139:12: error: 'min' was not declared in this scope
  else ans+=min(pv1-v1,pv2+1-v2)-min(pv1,pv2);
            ^~~
catdog.cpp:139:12: note: suggested alternative:
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from catdog.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   'std::min'
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
catdog.cpp: In function 'int neighbor(int)':
catdog.cpp:149:14: error: 'get_value' was not declared in this scope
  auto[v1,v2]=get_value(idx);
              ^~~~~~~~~
catdog.cpp:149:14: note: suggested alternative: 'si_value'
  auto[v1,v2]=get_value(idx);
              ^~~~~~~~~
              si_value
catdog.cpp:155:12: error: 'min' was not declared in this scope
  else ans+=min(pv1+v1-(V[idx]==1),pv2+v2-(V[idx]==2))-min(pv1,pv2);
            ^~~
catdog.cpp:155:12: note: suggested alternative:
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from catdog.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   'std::min'
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~