Submission #1122201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122201		FubuGold	Synchronization (JOI13_synchronization)	C++14	100 / 100	150 ms	21580 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100000;

struct BIT {
    vector<int> tree;
    int n;
    void init(int _n) {
        n = _n;
        tree.assign(n+1,0);
    }
    void update(int pos,int val) {
        for (;pos <= n;pos += pos & -pos) tree[pos] += val;
    }
    int query(int pos) {
        int sum = 0;
        for (;pos; pos -= pos & -pos) sum += tree[pos];
        return sum;
    }
    int query(int l,int r) {
        if (l > r) return 0;
        return query(r) - query(l-1);
    }
} tree;

int n,m,q;
pair<int,int> edge[MAXN+1];
vector<int> adj[MAXN+1];
int h[MAXN+1];
int sz[MAXN+1],pa[MAXN+1];
int cal_sz(int u) {
    sz[u] = 1;
    for (int i=0;i<adj[u].size();i++) {
        int v = adj[u][i];
        if (v == pa[u]) continue;
        h[v] = h[u] + 1;
        pa[v] = u;
        sz[u] += cal_sz(v);
    }
    return sz[u];
}

int d_hld[MAXN+1],pos[MAXN+1],root[MAXN+1];
int rev_pos[MAXN+1];
int cur_pos = 0;
void dfs_hld(int u) {
    pos[u] = ++cur_pos;
    rev_pos[cur_pos] = u;
    int mx_v = -1;
    for (int i=0;i<adj[u].size();i++) {
        int v = adj[u][i];
        if (v == pa[u]) continue;
        if (mx_v == -1 || sz[mx_v] < sz[v]) mx_v = v;
    }
    if (mx_v != -1) {
        d_hld[mx_v] = d_hld[u];
        root[mx_v] = root[u];
        dfs_hld(mx_v);
    }
    for (int i=0;i<adj[u].size();i++) {
        int v = adj[u][i];
        if (v == pa[u] || v == mx_v) continue;
        root[v] = v;
        d_hld[v] = d_hld[u] + 1;
        dfs_hld(v);
    }
}

int add[MAXN+1];
int val[MAXN+1];
bool flip[MAXN+1];

int find_highest(int u) {
//    cerr << u << '\n';
    while (u) {
        int r = root[u];
        if (tree.query(pos[r],pos[u]) == 0) {
            u = pa[r];
        }
        else break;
    }
//    cerr << "After: " << u << '\n';
    int l = pos[root[u]], r = pos[u];
    int ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (tree.query(mid,pos[u]) >= 1) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    if (ans == -1) return -1;
    return rev_pos[ans];
}

void query_add(int u,int v) {
    if (h[u] > h[v]) swap(u,v);
    int r = find_highest(u);
    add[r] += add[v];
    add[v] = 0;
    tree.update(pos[v],-1);
}
void query_rem(int u,int v) {
    if (h[u] > h[v]) swap(u,v);
    int r = find_highest(u);
    val[v] = val[r] + add[r];
    add[v] = 0;
    tree.update(pos[v],1);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m >> q;
    for (int i=1;i<n;i++) {
        int &x = edge[i].first, &y = edge[i].second;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    cal_sz(1);
    root[1] = 1;
    dfs_hld(1);
    tree.init(n);
    for (int i=1;i<=n;i++) {
        add[i] = 1;
        tree.update(i,1);
    }
    while (m--) {
        int x; cin >> x;
        if (flip[x]) {
            query_rem(edge[x].first,edge[x].second);
        }
        else {
            query_add(edge[x].first,edge[x].second);
        }
        flip[x] = !flip[x];
    }
    for (int i=1;i<=n;i++) val[i] += add[i];
    while (q--) {
        int x; cin >> x;
        cout << val[find_highest(x)] << '\n';
    }
    return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'int cal_sz(int)':
synchronization.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i=0;i<adj[u].size();i++) {
      |                  ~^~~~~~~~~~~~~~
synchronization.cpp: In function 'void dfs_hld(int)':
synchronization.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i=0;i<adj[u].size();i++) {
      |                  ~^~~~~~~~~~~~~~
synchronization.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i=0;i<adj[u].size();i++) {
      |                  ~^~~~~~~~~~~~~~

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