oj.uz

Submission #26087

# Submission time Handle Problem Language Result Execution time Memory
26087 2017-06-27T13:18:28 Z yosupo Synchronization (JOI13_synchronization) C++14
100 / 100
 529 ms 22164 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, int f[]) : sz(sz) {
        if (sz == 1) {
            ma = f[0];
            return;
        }
        l = new Node(sz/2, f);
        r = new Node(sz-sz/2, f+sz/2);
        ma = max(l->ma, r->ma);
    }
    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];
void dfs(int p, int b, int dp = 0) {
    dps[p] = dp;
    lid[p] = lc++;
    for (int d: g[p]) {
        if (d == b) continue;
        dfs(d, p, dp+1);
    }
    rid[lid[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, rid);
    auto rt = [&](int p) {
        return rmq->sea(p+1, rid[p]);
    };
    auto ad = [&](int p) {
        rmq->set(p, rid[p]);
    };
    auto er = [&](int p) {
        rmq->set(p, -1);
    };
    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);
        x = lid[x]; y = lid[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--; x = lid[x];
        printf("%d\n", vc[rt(x)]);
    }
    return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:64: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:67: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:84: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--; x = lid[x];
                        ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6664 KB Output is correct
2 Correct 0 ms 6664 KB Output is correct
3 Correct 0 ms 6664 KB Output is correct
4 Correct 0 ms 6664 KB Output is correct
5 Correct 0 ms 6664 KB Output is correct
6 Correct 0 ms 6796 KB Output is correct
7 Correct 19 ms 7588 KB Output is correct
8 Correct 19 ms 7588 KB Output is correct
9 Correct 19 ms 7588 KB Output is correct
10 Correct 343 ms 16168 KB Output is correct
11 Correct 379 ms 16168 KB Output is correct
12 Correct 296 ms 22156 KB Output is correct
13 Correct 239 ms 16584 KB Output is correct
14 Correct 229 ms 16168 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 19312 KB Output is correct
2 Correct 116 ms 19128 KB Output is correct
3 Correct 109 ms 22164 KB Output is correct
4 Correct 99 ms 22156 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6664 KB Output is correct
2 Correct 0 ms 6664 KB Output is correct
3 Correct 0 ms 6664 KB Output is correct
4 Correct 0 ms 6664 KB Output is correct
5 Correct 0 ms 6664 KB Output is correct
6 Correct 3 ms 6796 KB Output is correct
7 Correct 19 ms 8088 KB Output is correct
8 Correct 316 ms 22164 KB Output is correct
9 Correct 296 ms 22156 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 22160 KB Output is correct
2 Correct 116 ms 22116 KB Output is correct
3 Correct 156 ms 22164 KB Output is correct
4 Correct 153 ms 22156 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6664 KB Output is correct
2 Correct 0 ms 6664 KB Output is correct
3 Correct 0 ms 6664 KB Output is correct
4 Correct 0 ms 6664 KB Output is correct
5 Correct 3 ms 6796 KB Output is correct
6 Correct 29 ms 7588 KB Output is correct
7 Correct 529 ms 16168 KB Output is correct
8 Correct 366 ms 22160 KB Output is correct
9 Correct 353 ms 16584 KB Output is correct
10 Correct 286 ms 16168 KB Output is correct
11 Correct 186 ms 19308 KB Output is correct
12 Correct 163 ms 19312 KB Output is correct
13 Correct 119 ms 22164 KB Output is correct