Submission #26085

#	Time	Username	Problem	Language	Result	Execution time	Memory
26085		yosupo	Synchronization (JOI13_synchronization)	C++14	100 / 100	513 ms	22556 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40