| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 34998 | xooxooxooxoox | 스파이 (JOI13_spy) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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();
}