Submission #43013

#	Time	Username	Problem	Language	Result	Execution time	Memory
43013		ffresh	스파이 (JOI13_spy)	C++14	100 / 100	1181 ms	17360 KiB

spy

#include <bits/stdc++.h>

using namespace std;

const int N = 2005,M = 13;

int Count[N][N];

int depth[N];

int lca[N][M],value[N][M];

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

void makelca(int root,int p,int v){

	int u,i;

	lca[root][0] = p;
	value[root][0] = Count[root][v];
	depth[root] = depth[p]+1;

	for(i=1;i<M;++i){
		lca[root][i]= lca[lca[root][i-1]][i-1];
		value[root][i] = value[lca[root][i-1]][i-1] + value[root][i-1];
	}

	for(i=0;i<adj[root].size();++i){
		u = adj[root][i];
		makelca(u,root,v);
	}
}
int getvalue(int root){
	int d = depth[root],ret=0,i;
	for(i=0;i<M;++i){
		if(d&(1<<i)){

			ret+= value[root][i];
			root = lca[root][i];
		}
	}
	return ret;
}
vector<int> child[N];


int ret[N];
void dfs(int root,int P){
	child[root].push_back(root);

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

		dfs(u,P);

		if(child[u].size()>child[root].size()){
			swap(child[u],child[root]);
		}
		for(int j=0;j<child[u].size();++j){
			child[root].push_back(child[u][j]);
		}
		child[u].clear();
	}
	makelca(P,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,p,q;
	cin>>n>>m;
	int iroot,jroot;
	for(i=1;i<=n;++i){
		scanf("%d%d",&p,&q);
		if(p==0)iroot = i;
		if(q==0)jroot = i;

		if(p!=0)
			adj[p].push_back(i);
		if(q!=0)
			tdj[q].push_back(i);
	}
	for(i=0;i<m;++i){
		scanf("%d%d",&p,&q);
		++Count[p][q];
	}

	dfs(jroot,iroot);
	for(i=1;i<=n;++i)cout<<ret[i]<<endl;
}

Compilation message (stderr)

spy.cpp: In function 'void makelca(int, int, int)':
spy.cpp:28:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<adj[root].size();++i){
           ^
spy.cpp: In function 'void dfs(int, int)':
spy.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tdj[root].size();++i){
               ^
spy.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<child[u].size();++j){
                ^
spy.cpp:66: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:78:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p,&q);
                      ^
spy.cpp:88:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p,&q);
                      ^
spy.cpp:92:18: warning: 'jroot' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(jroot,iroot);
                  ^
spy.cpp:92:18: warning: 'iroot' may be used uninitialized in this function [-Wmaybe-uninitialized]

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