Submission #671745

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
671745	2022-12-13T16:14:03 Z	dsyz	스파이 (JOI13_spy)	C++17	100 / 100	104 ms	11376 KB

spy

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (2005)
ll N,M;
vector<ll> JOI[MAXN];
vector<ll> IOI[MAXN];
vector<ll> tasks[MAXN];
ll ans[MAXN];
ll preIOI[MAXN];
ll postIOI[MAXN];
ll cntIOI = 1;
ll ft[MAXN];
void update(ll l,ll r,ll v){
	r++;
	for(;l <= N;l += l & (-l)) ft[l] += v;
	for(;r <= N;r += r & (-r)) ft[r] -= v;
}
ll query(ll p){
	ll sum = 0;
	for(;p;p -= p & (-p)) sum += ft[p];
	return sum;
}
void IOIdfs(ll x,ll p){
	preIOI[x] = cntIOI++;
	for(auto u : IOI[x]){
		if(u != p){
			IOIdfs(u,x);
		}
	}
	postIOI[x] = cntIOI - 1;
}
void JOIdfs(ll x,ll p){
	for(auto i : tasks[x]){
		update(preIOI[i],postIOI[i],1);
	}
	ans[x] = query(preIOI[x]);
	for(auto u : JOI[x]){
		if(u != p){
			JOIdfs(u,x);
		}
	}
	for(auto i : tasks[x]){
		update(preIOI[i],postIOI[i],-1);
	}
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>M;
	ll bossJOI = 0;
	ll bossIOI = 0;
	for(ll p = 0;p < N;p++){
		ll j,i;
		cin>>j>>i;
		j--;
		i--;
		if(j == -1){
			bossJOI = p;
		}else{
			JOI[j].push_back(p);
		}
		if(i == -1){
			bossIOI = p;
		}else{
			IOI[i].push_back(p);
		}
	}
	IOIdfs(bossIOI,-1);
	for(ll m = 0;m < M;m++){
		ll JOIleader,IOIleader;
		cin>>JOIleader>>IOIleader;
		JOIleader--;
		IOIleader--;
		tasks[JOIleader].push_back(IOIleader);
	}
	JOIdfs(bossJOI,-1);
	for(ll i = 0;i < N;i++){
		cout<<ans[i]<<'\n';
	}
}

Subtask #1

10.0 / 10.0

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

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	852 KB	Output is correct
2	Correct	2 ms	812 KB	Output is correct
3	Correct	2 ms	596 KB	Output is correct
4	Correct	2 ms	612 KB	Output is correct
5	Correct	2 ms	676 KB	Output is correct
6	Correct	2 ms	596 KB	Output is correct
7	Correct	2 ms	724 KB	Output is correct
8	Correct	2 ms	684 KB	Output is correct

Subtask #3

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	11288 KB	Output is correct
2	Correct	87 ms	10164 KB	Output is correct
3	Correct	89 ms	10132 KB	Output is correct
4	Correct	96 ms	10376 KB	Output is correct
5	Correct	93 ms	10912 KB	Output is correct
6	Correct	79 ms	9532 KB	Output is correct
7	Correct	98 ms	11376 KB	Output is correct
8	Correct	104 ms	11328 KB	Output is correct