Submission #1162316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162316		dragst	Synchronization (JOI13_synchronization)	C++20	100 / 100	869 ms	26212 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;

long long n, m, k, p[200005], h[200005], u[200005], v[200005], b[200005];
long long sz[200005], nxt[200005], head[200005], chain[200005], pos[200005];
long long st[800005], a[200005], check[200005], tour[200005];
vector<long long> adj[200005];

void update(long long x, long long l, long long r, long long pos, long long k)
{
    if (l>r || l>pos || r<pos) {return;}
    else if (l==r) {st[x]+=k;}
    else
    {
        update(x*2, l, (l+r)/2, pos, k);
        update(x*2+1, (l+r)/2+1, r, pos, k);
        st[x]=st[x*2]+st[x*2+1];
    };
}

long long getsum(long long x, long long l, long long r, long long pos1, long long pos2)
{
    if (l>r || l>pos2 || r<pos1) {return 0LL;}
    else if (pos1<=l && r<=pos2) {return st[x];}
    else {return getsum(x*2, l, (l+r)/2, pos1, pos2)+getsum(x*2+1, (l+r)/2+1, r, pos1, pos2);};
}

void dfs(long long x)
{
    sz[x]=a[x]=1;
    for (auto y: adj[x])
    {
        if (y!=p[x])
        {
            h[y]=h[x]+1;
            p[y]=x;
            dfs(y);
            sz[x]+=sz[y];
            if (sz[y]>sz[nxt[x]]) {nxt[x]=y;};
        };
    };
}

void hld(long long x)
{
    if (head[m]==0) {head[m]=x;};
    chain[x]=m; tour[k]=x; pos[x]=k; k++;
    if (nxt[x]>0) {hld(nxt[x]);};
    for (auto y: adj[x])
    {
        if (y!=p[x] && y!=nxt[x])
        {
            m++;
            hld(y);
        };
    };
}

long long findset(long long x)
{
    long long i;
    while (getsum(1, 1, n, pos[head[chain[x]]], pos[x])==pos[x]-pos[head[chain[x]]]+1) {x=p[head[chain[x]]];};
    for (i=log2(pos[x]-pos[head[chain[x]]]); i>=0; i--)
    {
        if (getsum(1, 1, n, pos[x]-(1LL<<i), pos[x])==(1LL<<i)+1) {x=tour[pos[x]-(1LL<<i)];};
    };
    if (getsum(1, 1, n, pos[x], pos[x])==1) {return p[x];}
    else {return x;};
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long q1, q2, i, j;
    cin >> n >> q1 >> q2;
    for (i=1; i<n; i++)
    {
        cin >> u[i] >> v[i];
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    };
    dfs(1);
    hld(1);
    while (q1--)
    {
        cin >> i;
        if (check[i]==0)
        {
            check[i]=1;
            if (h[u[i]]>h[v[i]]) {swap(u[i], v[i]);};
            update(1, 1, n, pos[v[i]], 1);
            a[findset(v[i])]+=a[v[i]]-b[v[i]];
        }
        else
        {
            check[i]=0;
            if (h[u[i]]>h[v[i]]) {swap(u[i], v[i]);};
            update(1, 1, n, pos[v[i]], -1);
            j=findset(u[i]);
            a[v[i]]=b[v[i]]=a[j];
        };
    };
    while (q2--)
    {
        cin >> i;
        cout << a[findset(i)] << "\n";
    };
}

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