oj.uz

Submission #43064

# Submission time Handle Problem Language Result Execution time Memory
43064 2018-03-08T16:38:09 Z ffresh 스파이 (JOI13_spy) C++14
100 / 100
 1177 ms 27632 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1144 KB Output is correct
2 Correct 4 ms 1144 KB Output is correct
3 Correct 4 ms 1144 KB Output is correct
4 Correct 4 ms 1144 KB Output is correct
5 Correct 4 ms 1208 KB Output is correct
6 Correct 4 ms 1208 KB Output is correct
7 Correct 4 ms 1392 KB Output is correct
8 Correct 4 ms 1392 KB Output is correct
9 Correct 1 ms 1392 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 754 ms 17812 KB Output is correct
2 Correct 528 ms 17812 KB Output is correct
3 Correct 189 ms 17812 KB Output is correct
4 Correct 188 ms 17812 KB Output is correct
5 Correct 471 ms 17812 KB Output is correct
6 Correct 300 ms 17812 KB Output is correct
7 Correct 568 ms 17812 KB Output is correct
8 Correct 508 ms 17812 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1177 ms 27632 KB Output is correct
2 Correct 618 ms 27632 KB Output is correct
3 Correct 372 ms 27632 KB Output is correct
4 Correct 391 ms 27632 KB Output is correct
5 Correct 946 ms 27632 KB Output is correct
6 Correct 434 ms 27632 KB Output is correct
7 Correct 990 ms 27632 KB Output is correct
8 Correct 983 ms 27632 KB Output is correct