Submission #671745

#	Time	Username	Problem	Language	Result	Execution time	Memory
671745		dsyz	스파이 (JOI13_spy)	C++17	100 / 100	104 ms	11376 KiB

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