Submission #1117432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117432		FucKanh	Synchronization (JOI13_synchronization)	C++14	0 / 100	251 ms	35820 KiB

synchronization

#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pii pair<int,int>

using namespace std;

const int maxn = 1e5 + 2;
const int LG = 18;

int tin[maxn],tout[maxn],h[maxn],active[maxn],val[maxn], valid[maxn];
int pa[maxn][LG + 2];
pii e[maxn];
vector<int> a[maxn];
int n,m,q,T;

void dfs(int u, int par = -1) {
    tin[u] = ++T;
    for (int i = 1; i <= LG; i++) {
        pa[u][i] = pa[pa[u][i-1]][i-1];
    }
    for (int v : a[u]) if (v!=par) {
        pa[v][0] = u;
        h[v] = h[u] + 1;
        dfs(v,u);
    }
    tout[u] = ++T;
}

class BIT {
vector<int> t;
int n;
public:
    void init(int N) {
         n = N * 2;
         t.resize(n + 2, 0);
    }
    void update(int i, int v) {
        for (i;i<=n;i+=i&-i) t[i] += v;
    }
    int get(int i) {
        int re = 0;
        for (i;i;i-=i&-i) re += t[i];
        return re;
    }
};

BIT tree;

int path(int u) {
    return tree.get(tin[u]);
}

int getroot(int u) {
    int num = path(u);
    int dh = h[u];

    for (int i = LG; i >= 0; i--) {
        while (pa[u][i] && num - path(pa[u][i]) >= dh - h[pa[u][i]]) {
            u = pa[u][i];
        }
    }

    return u;
}

void add_edge(int id) {
    int u,v; tie(u,v) = e[id];
    if (h[u] > h[v]) swap(u,v);

    int rootu = getroot(u);
    int rootv = getroot(v);
    int tmp = val[rootu];
    val[rootu] += val[rootv] - valid[id];
    val[rootv] += tmp - valid[id];

    assert(val[rootu] == val[rootv]);
    valid[id] = val[rootu];

    tree.update(tin[v], 1);
    tree.update(tout[v], - 1);
}

void del_edge(int id) {
    int u,v; tie(u,v) = e[id];
    if (h[u] > h[v]) swap(u,v);

    val[v] = val[getroot(u)];

    tree.update(tin[v], -1);
    tree.update(tout[v], +1);
}

void solve() {
    cin >> n >> m >> q;
    tree.init(n);
    for (int i = 1; i <= n; i++) val[i]= 1;
    for (int i = 1;  i < n; i++) {
        int x,y; cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
        e[i] = {x,y};
    }
    h[1] = 1;
    dfs(1);
    for (int i = 1; i <= m; i++) {
        int id; cin >> id;
        if (active[id]) del_edge(id);
        else add_edge(id);
        active[id] = !active[id];
    }

    for (int i = 1; i < n; i++) {
        if (active[i]) del_edge(i);
    }

    for (int i = 1; i <= q; i++) {
        int x; cin >> x;
        cout << val[x] << '\n';
    }
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    solve();
    return 0;
}

Compilation message (stderr)

synchronization.cpp: In member function 'void BIT::update(long long int, long long int)':
synchronization.cpp:39:14: warning: statement has no effect [-Wunused-value]
   39 |         for (i;i<=n;i+=i&-i) t[i] += v;
      |              ^
synchronization.cpp: In member function 'long long int BIT::get(long long int)':
synchronization.cpp:43:14: warning: statement has no effect [-Wunused-value]
   43 |         for (i;i;i-=i&-i) re += t[i];
      |              ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40