# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
34998 | 2017-11-17T09:18:45 Z | xooxooxooxoox | 스파이 (JOI13_spy) | C++ | 0 ms | 0 KB |
#include<iostream> #include<cstdio> #include<cmath> #include<deque> #include<queue> #include<stack> #include<set> #include<vector> #include<algorithm> #include<array> #include<iomanip> #include<bitset> #define ll int #define ld long double #define maxN 2001 #define oo 1000000000000000001 #define Mod 1000000007 #define pii pair<ll,ll> #define fi first #define se second #define piii pair<ll,pii> #define fifi first.first #define fise first.second #define sefi second.first #define sese second.second #define endl '\n' #define gc getchar #define pc putchar using namespace std; ll n,m; ll x,y; vector<ll> f[maxN]; vector<ll> g[maxN]; bitset<500001> p[maxN]; bitset<500001> q[maxN]; void DFS1(ll u) { for(int v:f[u]) { p[v]|=p[u]; DFS1(v); } } void DFS2(ll u) { for(int v:g[u]) { q[v]|=q[u]; DFS2(v); } } void Enter() { cin>>n>>m; //read(n); //read(m); for(int i=1;i<=n;++i) { cin>>x>>y; //read(x); //read(y); f[x].push_back(i); g[y].push_back(i); } for(int i=0;i<m;++i) { cin>>x>>y; //read(x); //read(y); p[x].set(i); q[y].set(i); } DFS1(0); DFS2(0); for(int i=1;i<=n;++i) { ll ans=(p[i]&q[i]).count(); //writeln(ans); cout<<ans<<endl; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen("SPY.inp","r",stdin); //freopen("SPY.out","w",stdout); Enter(); }