oj.uz

Submission #41127

# Submission time Handle Problem Language Result Execution time Memory
41127 2018-02-13T03:18:36 Z DoanPhuDuc Synchronization (JOI13_synchronization) C++
100 / 100
 260 ms 70224 KB 
#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }

using namespace std;

typedef long long LL;
typedef pair <int, int> II;

const int N = 2e5 + 10;

int n, timer, m, q;
int x[N], y[N], V[N], ans[N], lst[N];

bool had[N];

vector <int> adj[N];

struct Edge {
    int u, v;
    Edge () {}
    Edge (int u, int v) : u(u), v(v) {}
} E[N];

struct SegmentTree {
    #define m ((l + r) >> 1)
    int st[4 * N];
    void Build(int k, int l, int r) {
        if (l == r) {
            int u = V[l];
            ans[u] = 1;
            st[k] = y[u];
            return;
        }
        Build(k << 1, l, m);
        Build(k << 1 | 1, m + 1, r);
        st[k] = max(st[k << 1], st[k << 1 | 1]);
    }
    void Assign(int k, int l, int r, int i, int v) {
        if (l == r) {
            st[k] = v;
            return;
        }
        if (i <= m) Assign(k << 1, l, m, i, v);
            else Assign(k << 1 | 1, m + 1, r, i, v);
        st[k] = max(st[k << 1], st[k << 1 | 1]);
    }
    int FindRoot(int k, int l, int r, int i, int v) {
        if (l > i || st[k] < v) return -1;
        if (l == r) return V[l];
        int x = FindRoot(k << 1 | 1, m + 1, r, i, v);
        if (x != -1) return x;
            else return FindRoot(k << 1, l, m, i, v);
    }
    #undef m
} ST;

void DFS(int u, int par = -1) {
    x[u] = ++timer;
    V[timer] = u;
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k]; if (v == par) continue;
        DFS(v, u);
    }
    y[u] = timer;
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d%d%d", &n, &m, &q);
    FOR(i, 1, n - 1) {
        int u, v; scanf("%d%d", &u, &v);
        E[i] = Edge(u, v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    timer = 0;
    DFS(1);
    FOR(i, 1, n) if (x[E[i].u] > x[E[i].v]) swap(E[i].u, E[i].v);
    ST.Build(1, 1, n);
    FOR(i, 1, m) {
        int id; scanf("%d", &id);
        int u = E[id].u, v = E[id].v;
        int r = ST.FindRoot(1, 1, n, x[u], y[u]);
        if (had[id] == false) {
            ans[r] += (ans[v] - lst[v]);
            ST.Assign(1, 1, n, x[v], 0);
        } else {
            ans[v] = lst[v] = ans[r];
            ST.Assign(1, 1, n, x[v], y[v]);
        }
        had[id] ^= 1;
    }
    while (q--) {
        int u; scanf("%d", &u);
        printf("%d\n", ans[ST.FindRoot(1, 1, n, x[u], y[u])]);
    }
    return 0;
}

Compilation message

synchronization.cpp: In function 'void DFS(int, int)':
synchronization.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
synchronization.cpp:66:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:78: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:80:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf("%d%d", &u, &v);
                                        ^
synchronization.cpp:90:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int id; scanf("%d", &id);
                                 ^
synchronization.cpp:103:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u; scanf("%d", &u);
                               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 5092 KB Output is correct
3 Correct 5 ms 5168 KB Output is correct
4 Correct 5 ms 5244 KB Output is correct
5 Correct 5 ms 5412 KB Output is correct
6 Correct 6 ms 5444 KB Output is correct
7 Correct 22 ms 6244 KB Output is correct
8 Correct 21 ms 6452 KB Output is correct
9 Correct 22 ms 6660 KB Output is correct
10 Correct 248 ms 15524 KB Output is correct
11 Correct 209 ms 17744 KB Output is correct
12 Correct 184 ms 24588 KB Output is correct
13 Correct 156 ms 24588 KB Output is correct
14 Correct 146 ms 24588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 27856 KB Output is correct
2 Correct 125 ms 29744 KB Output is correct
3 Correct 115 ms 33620 KB Output is correct
4 Correct 92 ms 35336 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35336 KB Output is correct
2 Correct 5 ms 35336 KB Output is correct
3 Correct 5 ms 35336 KB Output is correct
4 Correct 5 ms 35336 KB Output is correct
5 Correct 5 ms 35336 KB Output is correct
6 Correct 7 ms 35336 KB Output is correct
7 Correct 23 ms 35336 KB Output is correct
8 Correct 212 ms 39192 KB Output is correct
9 Correct 207 ms 41972 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 44868 KB Output is correct
2 Correct 130 ms 47128 KB Output is correct
3 Correct 135 ms 49500 KB Output is correct
4 Correct 128 ms 51836 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 51836 KB Output is correct
2 Correct 5 ms 51836 KB Output is correct
3 Correct 5 ms 51836 KB Output is correct
4 Correct 6 ms 51836 KB Output is correct
5 Correct 6 ms 51836 KB Output is correct
6 Correct 30 ms 51836 KB Output is correct
7 Correct 260 ms 51836 KB Output is correct
8 Correct 205 ms 57800 KB Output is correct
9 Correct 188 ms 57800 KB Output is correct
10 Correct 180 ms 58196 KB Output is correct
11 Correct 163 ms 63196 KB Output is correct
12 Correct 152 ms 65768 KB Output is correct
13 Correct 138 ms 70224 KB Output is correct