oj.uz

Submission #26085

# Submission time Handle Problem Language Result Execution time Memory
26085 2017-06-27T13:09:40 Z yosupo Synchronization (JOI13_synchronization) C++14
100 / 100
 513 ms 22556 KB 
#include <cstdio>
#include <vector>

using namespace std;
template<class T> using V = vector<T>;

struct Node {
    using NP = Node*;
    NP l, r; int sz;
    Node(int sz) : sz(sz) {
        ma = -1;
        if (sz == 1) return;
        l = new Node(sz/2);
        r = new Node(sz-sz/2);
    }
    int ma;
    void set(int k, int x) {
        if (sz == 1) {
            ma = x;
            return;
        }
        if (k < sz/2) {
            l->set(k, x);
        } else {
            r->set(k-sz/2, x);
        }
        ma = max(l->ma, r->ma);
    }
    int sea(int b, int x) {
        if (b <= 0 || ma < x) return -1;
        if (sz == 1) return 0;
        int u = r->sea(b - sz/2, x);
        if (u != -1) return u + sz/2;
        return l->sea(b, x);
    }
};


const int MN = 100100;

V<int> g[MN];

int lc, rc;
int dps[MN], lid[MN], rid[MN], lrev[MN];
void dfs(int p, int b, int dp = 0) {
    dps[p] = dp;
    lrev[lc] = p;
    lid[p] = lc++;
    for (int d: g[p]) {
        if (d == b) continue;
        dfs(d, p, dp+1);
    }
    rid[p] = rc++;
}


int vc[MN], uc[MN];

int e_x[MN], e_y[MN], e_on[MN];
int main() {
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    fill(vc, vc+n, 1);
    for (int i = 0; i < n-1; i++) {
        scanf("%d %d", e_x+i, e_y+i); e_x[i]--; e_y[i]--;
        g[e_x[i]].push_back(e_y[i]);
        g[e_y[i]].push_back(e_x[i]);
    }
    dfs(0, -1);
    Node* rmq = new Node(n);
    auto rt = [&](int p) {
        return lrev[rmq->sea(lid[p]+1, rid[p])];
    };
    auto ad = [&](int p) {
        rmq->set(lid[p], rid[p]);
    };
    auto er = [&](int p) {
        rmq->set(lid[p], -1);
    };
    for (int i = 0; i < n; i++) {
        ad(i);
    }
    for (int i = 0; i < m; i++) {
        int e;
        scanf("%d", &e); e--;
        int x = e_x[e], y = e_y[e];
        if (dps[x] < dps[y]) swap(x, y);
        if (!e_on[e]) {
            //inc
            vc[rt(y)] += vc[x] - uc[x];
            er(x);            
        } else {
            //dec
            vc[x] = uc[x] = vc[rt(y)];
            ad(x);
        }
        e_on[e] = 1-e_on[e];
    }

    for (int i = 0; i < q; i++) {
        int x;
        scanf("%d", &x); x--;
        printf("%d\n", vc[rt(x)]);
    }
    return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:62:34: 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:65:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", e_x+i, e_y+i); e_x[i]--; e_y[i]--;
                                     ^
synchronization.cpp:85:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &e); e--;
                        ^
synchronization.cpp:102:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x); x--;
                        ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7056 KB Output is correct
2 Correct 0 ms 7056 KB Output is correct
3 Correct 0 ms 7056 KB Output is correct
4 Correct 0 ms 7056 KB Output is correct
5 Correct 0 ms 7056 KB Output is correct
6 Correct 3 ms 7188 KB Output is correct
7 Correct 19 ms 7980 KB Output is correct
8 Correct 23 ms 7980 KB Output is correct
9 Correct 23 ms 7980 KB Output is correct
10 Correct 409 ms 16560 KB Output is correct
11 Correct 453 ms 16560 KB Output is correct
12 Correct 309 ms 22548 KB Output is correct
13 Correct 329 ms 16976 KB Output is correct
14 Correct 209 ms 16560 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 19704 KB Output is correct
2 Correct 133 ms 19520 KB Output is correct
3 Correct 99 ms 22556 KB Output is correct
4 Correct 129 ms 22548 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7056 KB Output is correct
2 Correct 0 ms 7056 KB Output is correct
3 Correct 0 ms 7056 KB Output is correct
4 Correct 0 ms 7056 KB Output is correct
5 Correct 0 ms 7056 KB Output is correct
6 Correct 0 ms 7188 KB Output is correct
7 Correct 26 ms 8476 KB Output is correct
8 Correct 313 ms 22552 KB Output is correct
9 Correct 346 ms 22556 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 22556 KB Output is correct
2 Correct 139 ms 22512 KB Output is correct
3 Correct 139 ms 22556 KB Output is correct
4 Correct 153 ms 22552 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7056 KB Output is correct
2 Correct 0 ms 7056 KB Output is correct
3 Correct 0 ms 7056 KB Output is correct
4 Correct 0 ms 7056 KB Output is correct
5 Correct 3 ms 7188 KB Output is correct
6 Correct 33 ms 7980 KB Output is correct
7 Correct 513 ms 16560 KB Output is correct
8 Correct 306 ms 22556 KB Output is correct
9 Correct 336 ms 16976 KB Output is correct
10 Correct 369 ms 16560 KB Output is correct
11 Correct 179 ms 19700 KB Output is correct
12 Correct 213 ms 19704 KB Output is correct
13 Correct 159 ms 22552 KB Output is correct