Submission #882396

#	Time	Username	Problem	Language	Result	Execution time	Memory
882396		12345678	Synchronization (JOI13_synchronization)	C++17	50 / 100	154 ms	24236 KiB

synchronization

#include <bits/stdc++.h>
 
using namespace std;
 
const int nx=1e5+5, kx=17;
int n, m, q, u[nx], v[nx], pa[nx][kx], lvl[nx], on[nx], dp[nx], l[nx], in[nx], out[nx], t, x, vs[nx];
vector<pair<int, int>> d[nx];
 
void dfs(int u, int p)
{
    lvl[u]=lvl[p]+1; pa[u][0]=p; dp[u]=1; in[u]=++t;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto [v, idx]:d[u]) if (v!=p) dfs(v, u);
    out[u]=t;
}

struct fenwick
{
    int d[nx];
    void add(int idx, int vl)
    {
        for (int i=idx; i<nx; i+=(i&-i)) d[i]+=vl;
    }
    int find(int idx)
    {
        int res=0;
        for (int i=idx; i>0; i-=(i&-i)) res+=d[i];
        return res;
    }
} f;

int findrt(int u)
{
    for (int i=kx-1; i>=0; i--) if (f.find(u)-f.find(pa[u][i])==lvl[u]-lvl[pa[u][i]]) u=pa[u][i];
    return u;
}

void dfs2(int u, int vl)
{
    vs[u]=1;
    dp[u]=vl;
    for (auto [v, idx]:d[u]) if (on[idx]&&v!=pa[u][0]) dfs2(v, vl); 
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    for (int i=1; i<n; i++) cin>>u[i]>>v[i], d[u[i]].push_back({v[i], i}), d[v[i]].push_back({u[i], i});
    dfs(1, 1);
    for (int i=1; i<=m; i++)
    {
        cin>>x;
        if (lvl[u[x]]>lvl[v[x]]) swap(u[x], v[x]);
        if (on[x])
        {
            l[v[x]]=dp[v[x]]=dp[findrt(u[x])];
            f.add(in[v[x]], -1);
            f.add(out[v[x]]+1, 1);
        }
        else
        {
            dp[findrt(u[x])]+=dp[v[x]]-l[v[x]];
            l[v[x]]=0;
            f.add(in[v[x]], 1);
            f.add(out[v[x]]+1, -1);
        }
        on[x]=!on[x];
    }
    for (int i=1; i<=n; i++) if (!vs[i]) dfs2(findrt(i), dp[findrt(i)]);
    while (q--) cin>>x, cout<<dp[x]<<'\n';
}

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