oj.uz

Submission #40354

# Submission time Handle Problem Language Result Execution time Memory
40354 2018-01-31T09:48:27 Z krauch Synchronization (JOI13_synchronization) C++14
40 / 100
 8000 ms 55432 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int, int > PII;

#define F first
#define S second
#define mkp make_pair
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)

const ll ool = 1e18 + 9;
const int N = 3e5 + 3, oo = 1e9 + 9;

int n, m, Q;
bool open[N];
vector < PII > g[N], vec[N];

int dfs(int v, int par, int X) {
    int res = 1;
    for (auto it : g[v]) {
        int to = it.F;
        if (to == par) continue;
        int pos = lower_bound(all(vec[it.S]), PII(X, 0)) - vec[it.S].begin() - 1;
        if (pos < 0) continue;
        res += dfs(to, v, (vec[it.S][pos].S ? X : vec[it.S][pos].F  ));
    }
    return res;
}

int main() {

    #ifdef krauch
        freopen("input.txt", "r", stdin);
    #endif

    scanf("%d%d%d", &n, &m, &Q);
    forn(i, 1, n - 1) {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x].eb(y, i);
        g[y].eb(x, i);
    }

    forn(i, 1, m) {
        int x;
        scanf("%d", &x);
        open[x] ^= 1;
        vec[x].eb(i, open[x]);
    }

    forn(i, 1, Q) {
        int x;
        scanf("%d", &x);
        cout << dfs(x, 0, m + 1) << "\n";
    }

    return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:42:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &Q);
                                ^
synchronization.cpp:45:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
                              ^
synchronization.cpp:52:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
                        ^
synchronization.cpp:59:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
                        ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14328 KB Output is correct
2 Correct 14 ms 14432 KB Output is correct
3 Correct 13 ms 14636 KB Output is correct
4 Correct 13 ms 14636 KB Output is correct
5 Correct 13 ms 14636 KB Output is correct
6 Correct 14 ms 14700 KB Output is correct
7 Correct 23 ms 15612 KB Output is correct
8 Correct 23 ms 15872 KB Output is correct
9 Correct 22 ms 16244 KB Output is correct
10 Correct 145 ms 25064 KB Output is correct
11 Correct 149 ms 27528 KB Output is correct
12 Correct 111 ms 29108 KB Output is correct
13 Correct 104 ms 31824 KB Output is correct
14 Correct 134 ms 32864 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 36580 KB Output is correct
2 Correct 84 ms 37140 KB Output is correct
3 Correct 81 ms 41836 KB Output is correct
4 Correct 88 ms 42600 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 42600 KB Output is correct
2 Correct 13 ms 42600 KB Output is correct
3 Correct 15 ms 42600 KB Output is correct
4 Correct 13 ms 42600 KB Output is correct
5 Correct 13 ms 42600 KB Output is correct
6 Correct 14 ms 42600 KB Output is correct
7 Correct 26 ms 42600 KB Output is correct
8 Correct 168 ms 42600 KB Output is correct
9 Correct 163 ms 44448 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 44480 KB Output is correct
2 Execution timed out 8013 ms 52256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 52256 KB Output is correct
2 Correct 12 ms 52256 KB Output is correct
3 Correct 12 ms 52256 KB Output is correct
4 Correct 13 ms 52256 KB Output is correct
5 Correct 16 ms 52256 KB Output is correct
6 Correct 155 ms 52256 KB Output is correct
7 Correct 3988 ms 52256 KB Output is correct
8 Correct 175 ms 52524 KB Output is correct
9 Execution timed out 8055 ms 55432 KB Time limit exceeded
10 Halted 0 ms 0 KB -