Submission #689974

#	Time	Username	Problem	Language	Result	Execution time	Memory
689974		vjudge1	Synchronization (JOI13_synchronization)	C++17	100 / 100	608 ms	36036 KiB

synchronization

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
typedef pair<int,int> ii;
#define ff first
#define ss second
ii e[maxn];
int n,m,q;
vector <int> adj[maxn];
int d[maxn],c[maxn];
int par[19][maxn];
int in[maxn],out[maxn],cnt;
int f[maxn];
bool dau[maxn];

void update(int x, int val)
{
    while (x<=n)
    {
        f[x]+=val;
        x+=(x&-x);
    }
}

int get(int x)
{
    int temp=0;
    while (x>0)
    {
        temp+=f[x];
        x-=(x&-x);
    }
    return temp;
}

void updaterange(int l, int r, int val)
{
    update(l,val); update(r+1,-val);
}

void dfs(int x, int p)
{
    in[x]=++cnt;
    par[0][x] = p;
    for (int i=1; i<=18; i++) par[i][x]=par[i-1][par[i-1][x]];
    for (int i:adj[x])
        if (i!=p) dfs(i,x);
    out[x]=cnt;
}

int get_root(int x)
{
    int u=x; int val=get(in[u]);
    for (int i=18; i>=0; i--)
        if (get(in[par[i][u]])==get(in[x])) u=par[i][u];
    return u;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m>>q;
    for (int i=1; i<n; i++)
    {
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        e[i]={u,v};
    }
    fill_n(d,n+1,1);
    fill_n(dau,n+1,0);
    dfs(1,1);
    for (int i=1; i<=n; i++) updaterange(in[i],out[i],1);
    for (int i=1; i<=m; i++)
    {
        int id; cin>>id;
        int u=e[id].ff; int v=e[id].ss;
        if (v==par[0][u]) swap(u,v);
//        cout<<u<<" -> "<<v<<'\n';
        if (!dau[id])
        {
            d[get_root(u)]+=d[v]-c[v];
        }
        else
        {
            d[v]=c[v]=d[get_root(u)];
        }
//        cout<<i<<": ";
//        for (int j=1; j<=n; j++) cout<<d[j]<<' '; cout<<'\n';
        if (!dau[id]) updaterange(in[v],out[v],-1);
        else updaterange(in[v],out[v],1);
        dau[id]^=1;
    }
    for (int i=1; i<=q; i++)
    {
        int u; cin>>u;
        u=get_root(u);
        cout<<d[u]<<'\n';
    }
}

Compilation message (stderr)

synchronization.cpp: In function 'long long int get_root(long long int)':
synchronization.cpp:54:18: warning: unused variable 'val' [-Wunused-variable]
   54 |     int u=x; int val=get(in[u]);
      |                  ^~~

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