# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
35003 | 2017-11-17T09:19:44 Z | nad312 | 스파이 (JOI13_spy) | C++11 | 0 ms | 0 KB |
#include<bits/stdc++.h> using namespace std; typedef int lli; lli a, b, c, d, e, f, g, h, chia=64; long long int x[2009][7820]={}, y[2009][7820]={}; vector<lli> Dx[2009], Dy[2009]; lli next() { register char ch=getchar(); lli l=0; while(ch<'0'||ch>'9') { ch=getchar(); } while(ch>='0'&&ch<='9') { l=l*10+ch-'0'; ch=getchar(); } return l; } void DSFx(lli u, lli k) { x[u][k/chia]=x[u][k/chia]|((long long int)1<<(k%chia)); for(auto v: Dx[u]) { DSFx(v, k; } } void DSFy(lli u, lli k) { y[u][k/chia]=y[u][k/chia]|((long long int)1<<(k%chia)); for(auto v: Dy[u]) { DSFy(v, k); } } void Inp() { a=next(); b=next(); for(int i=1;i<=a;i++) { c=next(); d=next(); Dx[c].push_back(i); Dy[d].push_back(i); } for(int i=1;i<=b;i++) { c=next(); d=next(); DSFx(c, i); DSFy(d, i); } } void Solve() { h=b/chia; for(int i=1;i<=a;i++) { d=0; for(int j=0;j<=h;j++) { c=(x[i][j]&y[i][j]); d=d+__builtin_popcount(c); } cout<<d<<'\n'; } } int main() { freopen("test.inp","r",stdin); Inp(); Solve(); }