oj.uz

Submission #35010

# Submission time Handle Problem Language Result Execution time Memory
35010 2017-11-17T09:22:20 Z xooxooxooxoox 스파이 (JOI13_spy) C++14
100 / 100
 369 ms 246684 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
template<typename T> inline void read(T &x) {
    char c;
    bool neg = false;
    while (!isdigit(c = getchar()) && c != '-');
    x = 0;
    if (c == '-') {
        neg = true;
        c = getchar();
    }
    do {
        x = x * 10 + c - '0';
    } while (isdigit(c = getchar()));
    if (neg) x = -x;
}
template<typename T> inline void write(T x) {
    if (x < 0) {
        putchar('-');
        write(-x);return;
    }
    if (x < 10) {
        putchar(char(x + 48));
    }
    else {
        write(x/10);
        putchar(char(48 + x%10));
    }
}
template<typename T> inline void writeln(T x) {
    write(x);
    putchar('\n');
}
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();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 246552 KB Output is correct
2 Correct 13 ms 246552 KB Output is correct
3 Correct 16 ms 246552 KB Output is correct
4 Correct 13 ms 246552 KB Output is correct
5 Correct 16 ms 246552 KB Output is correct
6 Correct 16 ms 246552 KB Output is correct
7 Correct 19 ms 246552 KB Output is correct
8 Correct 13 ms 246552 KB Output is correct
9 Correct 0 ms 246552 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 246684 KB Output is correct
2 Correct 169 ms 246684 KB Output is correct
3 Correct 149 ms 246552 KB Output is correct
4 Correct 163 ms 246552 KB Output is correct
5 Correct 169 ms 246552 KB Output is correct
6 Correct 183 ms 246552 KB Output is correct
7 Correct 136 ms 246684 KB Output is correct
8 Correct 143 ms 246684 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 246684 KB Output is correct
2 Correct 213 ms 246684 KB Output is correct
3 Correct 306 ms 246552 KB Output is correct
4 Correct 289 ms 246552 KB Output is correct
5 Correct 326 ms 246552 KB Output is correct
6 Correct 219 ms 246552 KB Output is correct
7 Correct 363 ms 246684 KB Output is correct
8 Correct 369 ms 246684 KB Output is correct