Submission #689824

#	Time	Username	Problem	Language	Result	Execution time	Memory
689824		vjudge1	Synchronization (JOI13_synchronization)	C++17	100 / 100	467 ms	25016 KiB

synchronization

#define taskname "Synchronization"
#include <bits/stdc++.h>
#define ii pair<int,int>
#define ff first
#define ss second

using namespace std;
const int maxn = 1e5 + 10;
vector<int> adj[maxn];
int p[20][maxn], fen[maxn], sz[maxn], mark[maxn], in[maxn], out[maxn], pre[maxn], cnt, n, m, q;
ii e[maxn];

void DFS(int u = 1, int pa = 0)
{
    sz[u] = 1;
    in[u] = ++cnt;
    for (int v: adj[u]) if (v != pa) p[0][v] = u, DFS(v, u);
    out[u] = cnt;
}

inline void upd(int pos, int val) {
    for (; pos<=n; pos+=pos&-pos) fen[pos] += val;
}

inline int ask(int pos) {
    int ans = 0;
    for (; pos; pos-=pos&-pos) ans += fen[pos];
    return ans;
}

inline int fp(int u) {
    int ans = u, cc = ask(in[u]);
    for (int i=19; i>=0; i--)
        if (p[i][ans] && ask(in[p[i][ans]]) == cc)
            ans = p[i][ans];
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m>>q;
    for (int i=1, u, v; i<n; i++) cin>>u>>v, adj[u].emplace_back(v), adj[v].emplace_back(u), e[i] = {u, v};
    DFS();
    for (int j=1; (1<<j)<=n; j++)
        for (int i=1; i<=n; i++)
            p[j][i] = p[j-1][p[j-1][i]];
    for (int i=1; i<=n; i++) upd(in[i], 1), upd(out[i]+1, -1);
    for (int i=1, id; i<=m; i++)
    {
        cin>>id;
        auto [u, v] = e[id];
        if (in[u] > in[v]) swap(u, v);
//        cerr<<"QUERY: "<<u<<" "<<v<<"\n";
        u = fp(u);
//        cerr<<"PAR: "<<ask(u)<<" "<<u<<"\n";
        if (mark[id])
        {
            sz[v] = pre[v] = sz[u];
            upd(in[v], +1);
            upd(out[v]+1, -1);
        }
        else
        {
            sz[u] += sz[v] - pre[v];
            upd(in[v], -1);
            upd(out[v]+1, +1);
        }
        mark[id] ^= 1;
//        cerr<<"REPORT\n";
//        for (int i=1; i<=n; i++) cerr<<sz[i]<<" "; cerr<<"\n";
    }
//    cerr<<"EDGE:\n";
//    for (int i=1; i<n; i++) if (mark[i]) cerr<<"EXIST: "<<e[i].ff<<" "<<e[i].ss<<"\n";
//    for (int i=1; i<=n; i++) cerr<<"CHECK: "<<i<<" "<<ask(in[i])
    for (int i=1, id; i<=q; i++) cin>>id, cout<<sz[fp(id)]<<"\n";
}

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