oj.uz

Submission #24907

# Submission time Handle Problem Language Result Execution time Memory
24907 2017-06-17T05:41:49 Z khsoo01 스파이 (JOI13_spy) C++11
100 / 100
 286 ms 23176 KB 
#include<bits/stdc++.h>
using namespace std;

int n, m, ans[2005];

struct query {int s, e, x;};
vector<query> swp[2005];

struct tree {
	int rt, s[2005], e[2005], inv[2005], cc;
	vector<int> adj[2005];
	void renum (int cur) {
		s[cur] = ++cc;
		inv[cc] = cur;
		for(auto &nxt : adj[cur]) {
			renum(nxt);
		}
		e[cur] = cc;
	}
} t1, t2;

struct segtree {
	int val[10005], lim;
	void init () {
		for(lim=1;lim<=n;lim<<=1);
	}
	void update (int S, int E, int X) {
		S += lim; E += lim;
		while(S <= E) {
			if(S % 2 == 1) val[S++] += X;
			if(E % 2 == 0) val[E--] += X;
			S >>= 1; E >>= 1;
		}
	}
	int query (int P) {
		int ret = 0; P += lim;
		while(P) {
			ret += val[P];
			P >>= 1;
		}
		return ret;
	}
} seg;

int main()
{
	scanf("%d%d",&n,&m);
	seg.init();
	for(int i=1;i<=n;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		if(!A) t1.rt = i;
		else t1.adj[A].push_back(i);
		if(!B) t2.rt = i;
		else t2.adj[B].push_back(i);
	}
	t1.renum(t1.rt);
	t2.renum(t2.rt);
	for(int i=1;i<=m;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		swp[t2.s[B]].push_back({t1.s[A], t1.e[A], 1});
		swp[t2.e[B]+1].push_back({t1.s[A], t1.e[A], -1});
	}
	for(int i=1	;i<=n;i++) {
		for(auto &Q : swp[i]) {
			seg.update(Q.s, Q.e, Q.x);
		}
		int I = t2.inv[i];
		ans[I] = seg.query(t1.s[I]);
	}
	for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}

Compilation message

spy.cpp: In function 'int main()':
spy.cpp:47:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
spy.cpp:51: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:61:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
                      ^

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2520 KB Output is correct
2 Correct 0 ms 2528 KB Output is correct
3 Correct 0 ms 2388 KB Output is correct
4 Correct 0 ms 2388 KB Output is correct
5 Correct 3 ms 2388 KB Output is correct
6 Correct 0 ms 2388 KB Output is correct
7 Correct 3 ms 2520 KB Output is correct
8 Correct 0 ms 2388 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 17820 KB Output is correct
2 Correct 146 ms 20908 KB Output is correct
3 Correct 196 ms 17724 KB Output is correct
4 Correct 179 ms 23176 KB Output is correct
5 Correct 239 ms 20272 KB Output is correct
6 Correct 146 ms 21760 KB Output is correct
7 Correct 286 ms 19824 KB Output is correct
8 Correct 286 ms 20392 KB Output is correct