Submission #43064

#	Time	Username	Problem	Language	Result	Execution time	Memory
43064		ffresh	스파이 (JOI13_spy)	C++14	100 / 100	1177 ms	27632 KiB

spy

#include <bits/stdc++.h>

using namespace std;

const int N = 2005,M = 12;

vector<int> child[N],adj[N],tdj[N];

int lca[N][M], sum[N][M],depth[N];

int Count[N][N];

void makelca(int root,int p,int K){
	depth[root]= depth[p]+1;

	lca[root][0]= p;
	sum[root][0]= Count[root][K];

	for(int i=1;i<M;++i)
		lca[root][i]= lca[lca[root][i-1]][i-1],
		sum[root][i] = sum[root][i-1] + sum[lca[root][i-1]][i-1];
	for(int i=0;i<adj[root].size();++i){
		int u = adj[root][i];

		makelca(u,root,K);
	}
}
int getvalue(int root){
	int ret=0;
	int d = depth[root];

	for(int i=0;i<M;++i){
		if(d&(1<<i)){
			ret += sum[root][i];
			root = lca[root][i];
		}
	}
	return ret;
}

int ret[N];
void dfs(int root,int K){

	child[root].push_back(root);
	for(int i=0;i<tdj[root].size();++i){
		int u= tdj[root][i];

		dfs(u,K);

		for(int j=0;j<child[u].size();++j)
			child[root].push_back(child[u][j]);
		child[u].clear();
	}
	makelca(K,0,root);

	for(int i=0;i<child[root].size();++i)
	{
		int u = child[root][i];
		ret[u]+=getvalue(u);
	}
}

int main(){
	//freopen("input.txt","r",stdin);
	int n,m,i,a,b;
	cin>>n>>m;
	int p,q;
	for(i=1;i<=n;++i){
		scanf("%d%d",&a,&b);
		if(a==0)p= i;
		else
			adj[a].push_back(i);
		if(b==0)q = i;
		else
			tdj[b].push_back(i);
	}
	for(i=0;i<m;++i){
		scanf("%d%d",&a,&b);
		++Count[a][b];
	}
	dfs(q,p);
	for(i=1;i<=n;++i)cout<<ret[i]<<endl;
}

Compilation message (stderr)

spy.cpp: In function 'void makelca(int, int, int)':
spy.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[root].size();++i){
               ^
spy.cpp: In function 'void dfs(int, int)':
spy.cpp:45:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tdj[root].size();++i){
               ^
spy.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<child[u].size();++j)
                ^
spy.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<child[root].size();++i)
               ^
spy.cpp: In function 'int main()':
spy.cpp:69:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
                      ^
spy.cpp:78:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
                      ^
spy.cpp:81:10: warning: 'q' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(q,p);
          ^
spy.cpp:81:10: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70