Submission #41127

#	Time	Username	Problem	Language	Result	Execution time	Memory
41127		DoanPhuDuc	Synchronization (JOI13_synchronization)	C++98	100 / 100	260 ms	70224 KiB

synchronization

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

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