제출 #1285097

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285097		kerem	스파이 (JOI13_spy)	C++20	100 / 100	95 ms	7168 KiB

spy

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 2000
#define inf (int)1e15
typedef pair<int,int> pii;

vector<int> joi[N+5],ioi[N+5],q[N+5];
int ans[N+5],st[2*N],in[N+5],out[N+5],timer=-1;
void update(int l,int r,int d){
	l+=N;r+=N+1;
	while(l<r){
		if(l&1) st[l++]+=d;
		if(r&1) st[--r]+=d;
		l>>=1;r>>=1;
	}
}
int query(int x){
	x+=N;
	int ans=0;
	while(x){
		ans+=st[x];
		x>>=1;
	}
	return ans;
}
void init(int x){	
	in[x]=++timer;
	for(auto i:ioi[x])	
		init(i);
	out[x]=timer;
}
void calc(int x){
	for(auto i:q[x])
		update(in[i],out[i],1);
	ans[x]=query(in[x]);
	for(auto i:joi[x])	
		calc(i);
	for(auto i:q[x])
		update(in[i],out[i],-1);
}
void solve(){
	int n,m;
	cin >> n >> m;
	int rj,ri;
	for(int i=1;i<=n;i++){
		int pj,pi;
		cin >> pj >> pi;
		if(pj==0) rj=i;
		if(pi==0) ri=i;
		joi[pj].pb(i);
		ioi[pi].pb(i);
	}
	for(int i=0;i<m;i++){
		int x,y;
		cin >> x >> y;
		q[x].pb(y);
	}
	init(ri);
	calc(rj);
	for(int i=1;i<=n;i++)
		cout << ans[i] << endl;
}
int32_t main(){
	//~ freopen("hopscotch.in","r",stdin);
	//~ freopen("hopscotch.out","w",stdout);
	
	cout << fixed << setprecision(0);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70