oj.uz

답안 #34977

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
34977 2017-11-17T09:05:22 Z xooxooxooxoox 스파이 (JOI13_spy) C++11
10 / 100
 133 ms 262144 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;
/// ***************************** FAST I/O *****************************
inline void read(ll &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for (;((c<48 || c>57) && c != '-') ;c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}

inline void writeln(ll x)
{
     char buffor[21];
     register int i=0;
     int neg=0; if (x<0) {neg=1; x= -x;}
     do{
           buffor[i++]=(x%10)+'0';
           x/=10;
        } while(x);
       i--;
       if (neg) pc('-');
       while(i>=0) pc(buffor[i--]);
       pc('\n');
}
/// ***************************** FAST I/O *****************************
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 i=0;i<f[u].size();++i)
    {
        p[f[u][i]]=(p[f[u][i]]|p[u]);
        DFS1(f[u][i]);
    }
}
void DFS2(ll u)
{
    for(int i=0;i<g[u].size();++i)
    {
        q[g[u][i]]=(q[g[u][i]]|q[u]);
        DFS2(g[u][i]);
    }
}
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);
    }

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("SPY.inp","r",stdin);
    //freopen("SPY.out","w",stdout);
    Enter();
}

Compilation message

spy.cpp: In function 'void DFS1(int)':
spy.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<f[u].size();++i)
                  ^
spy.cpp: In function 'void DFS2(int)':
spy.cpp:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[u].size();++i)
                  ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 258704 KB Output is correct
2 Correct 33 ms 258704 KB Output is correct
3 Correct 26 ms 246608 KB Output is correct
4 Correct 13 ms 246608 KB Output is correct
5 Correct 23 ms 247460 KB Output is correct
6 Correct 33 ms 247584 KB Output is correct
7 Correct 19 ms 251800 KB Output is correct
8 Correct 36 ms 248560 KB Output is correct
9 Correct 0 ms 246548 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 3 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 133 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -