Submission #24907

#	Time	Username	Problem	Language	Result	Execution time	Memory
24907		khsoo01	스파이 (JOI13_spy)	C++11	100 / 100	286 ms	23176 KiB

spy

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70