oj.uz

Submission #34930

# Submission time Handle Problem Language Result Execution time Memory
34930 2017-11-17T07:50:31 Z nickyrio 스파이 (JOI13_spy) C++14
100 / 100
 403 ms 249440 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<=b ; i++)
#define FORD(i, a, b) for (int i = a; i>=b; i--)
#define REP(i, a) for (int i = 0; i<a; i++)
#define M 501000
#define N 2020
#define pp pair<int, int>
#define IO cin.tie(NULL);cout.tie(NULL);
#define bit(S, i) ((S >> i) & 1)
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;

int n, m, x;
vector<int> a[N], b[N];
bitset<M> bsa[N], bsb[N], now;

void dfsa(int u, int p) {
    for (int v : a[u]) if (v != p) {
        bsa[v] |= bsa[u];
        dfsa(v, u);
    }
}

void dfsb(int u, int p) {
    for (int v : b[u]) if (v != p) {
        bsb[v] |= bsb[u];
        dfsb(v, u);
    }
}

int main() {
    IO;
    int ra, rb;

    read(n);read(m);
    FOR(i, 1, n) {
        read(x);
        if (x == 0) ra = i;
        else a[x].push_back(i);
        read(x);
        if (x == 0) rb = i;
        else b[x].push_back(i);
    }
    REP(i, m) {
        read(x);
        bsa[x].set(i);
        read(x);
        bsb[x].set(i);
    }
    dfsa(ra, -1);
    dfsb(rb, -1);
    FOR(i, 1, n) {
        now = bsa[i] & bsb[i];
        writeln(now.count());
    }
}

Compilation message

spy.cpp: In function 'int main()':
spy.cpp:81:17: warning: 'rb' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dfsb(rb, -1);
                 ^
spy.cpp:80:17: warning: 'ra' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dfsa(ra, -1);
                 ^

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 249440 KB Output is correct
2 Correct 163 ms 249440 KB Output is correct
3 Correct 159 ms 249276 KB Output is correct
4 Correct 166 ms 249276 KB Output is correct
5 Correct 166 ms 249408 KB Output is correct
6 Correct 159 ms 249408 KB Output is correct
7 Correct 183 ms 249408 KB Output is correct
8 Correct 163 ms 249408 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 249440 KB Output is correct
2 Correct 219 ms 249440 KB Output is correct
3 Correct 323 ms 249276 KB Output is correct
4 Correct 293 ms 249276 KB Output is correct
5 Correct 396 ms 249408 KB Output is correct
6 Correct 226 ms 249408 KB Output is correct
7 Correct 393 ms 249408 KB Output is correct
8 Correct 366 ms 249408 KB Output is correct