Submission #88165

#	Time	Username	Problem	Language	Result	Execution time	Memory
88165		Bodo171	Synchronization (JOI13_synchronization)	C++14	100 / 100	963 ms	21708 KiB

synchronization

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
vector<int> v[nmax];
int l[nmax],r[nmax],lev[nmax],aib[nmax],a[nmax],b[nmax],state[nmax],sub[nmax],old[nmax],know[nmax];
int tt[20][nmax];
int n,nr,m,q,i,j,x,y,L;
void dfs(int x)
{
    l[x]=++nr;
    for(int i=0;i<v[x].size();i++)
        if(!l[v[x][i]])
    {
        lev[v[x][i]]=lev[x]+1;
        tt[0][v[x][i]]=x;
        dfs(v[x][i]);
    }
    r[x]=nr;
}
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int poz,int val)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
        aib[idx]+=val;
}
int compute(int poz)
{
    int ret=0;
    for(int idx=poz;idx>0;idx-=lbit(idx))
        ret+=aib[idx];
    return ret;
}
bool check(int x,int y)
{
    return (compute(l[y])-compute(l[x])==lev[y]-lev[x]);
}
int anc(int node)
{
    for(int p=16;p>=0;p--)
        if(tt[p][node]&&check(tt[p][node],node))
         node=tt[p][node];
    return node;
}
void bmw()
{
    for(i=1;i<17;i++)
        for(j=1;j<=n;j++)
          tt[i][j]=tt[i-1][tt[i-1][j]];
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m>>q;
    for(i=1;i<=n-1;i++)
    {
        cin>>x>>y;
        a[i]=x,b[i]=y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        know[i]=sub[i]=1;
    dfs(1);
    bmw();
    for(i=1;i<=m;i++)
    {
        cin>>nr;
        if(lev[a[nr]]<lev[b[nr]])
            swap(a[nr],b[nr]);
        x=a[nr];
        if(state[nr]==0)
        {
            update(l[x],1);update(r[x]+1,-1);
            L=anc(x);
            sub[L]+=(sub[x]-old[x]);
            know[L]+=(sub[x]-old[x]);
        }
        else
        {
            L=anc(x);
            update(l[x],-1);update(r[x]+1,1);
            know[x]=know[L];old[x]=sub[x];
        }
        state[nr]^=1;
    }
    for(i=1;i<=n;i++)
    {
        know[i]=know[anc(i)];
    }
    for(i=1;i<=q;i++)
    {
        cin>>x;
        cout<<know[x]<<'\n';
    }
    return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'void dfs(int)':
synchronization.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~

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