oj.uz

Submission #43013

# Submission time Handle Problem Language Result Execution time Memory
43013 2018-03-08T05:34:23 Z ffresh 스파이 (JOI13_spy) C++14
100 / 100
 1181 ms 17360 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1016 KB Output is correct
2 Correct 5 ms 1016 KB Output is correct
3 Correct 6 ms 1016 KB Output is correct
4 Correct 4 ms 1016 KB Output is correct
5 Correct 4 ms 1044 KB Output is correct
6 Correct 4 ms 1044 KB Output is correct
7 Correct 5 ms 1228 KB Output is correct
8 Correct 5 ms 1228 KB Output is correct
9 Correct 2 ms 1228 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 7388 KB Output is correct
2 Correct 568 ms 7388 KB Output is correct
3 Correct 244 ms 7388 KB Output is correct
4 Correct 229 ms 7388 KB Output is correct
5 Correct 570 ms 7388 KB Output is correct
6 Correct 369 ms 7388 KB Output is correct
7 Correct 595 ms 7804 KB Output is correct
8 Correct 572 ms 7804 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1181 ms 17360 KB Output is correct
2 Correct 634 ms 17360 KB Output is correct
3 Correct 411 ms 17360 KB Output is correct
4 Correct 401 ms 17360 KB Output is correct
5 Correct 937 ms 17360 KB Output is correct
6 Correct 490 ms 17360 KB Output is correct
7 Correct 1038 ms 17360 KB Output is correct
8 Correct 975 ms 17360 KB Output is correct