Submission #1008621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008621		vjudge1	Synchronization (JOI13_synchronization)	C++17	100 / 100	131 ms	25488 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=(j);i<=(k);i++)
#define for2(i,j,k) for(int i=(j);i>=(k);i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=1e5+6;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=123456789;

int n,m,q;
int in[maxn],out[maxn],id[maxn*2];
int dp[maxn],last[maxn];
int s[maxn*8];
void build(int x,int l,int r)
{
    if(l==r)
    {
        s[x]=out[id[l]];
        return;
    }
    int mid=l+r>>1;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    s[x]=max(s[x*2],s[x*2+1]);
}

void update(int x,int l,int r,int pos,int val)
{
    if(l==r)
    {
        s[x]=val;
        return;
    }
    int mid=l+r>>1;
    if(mid>=pos)update(x*2,l,mid,pos,val);
    else update(x*2+1,mid+1,r,pos,val);
    s[x]=max(s[x*2],s[x*2+1]);
}

int query(int x,int l,int r,int pos,int val)
{
    if(l>pos || s[x] <= val)return 0;
    if(l==r)return l;
    int mid=l+r>>1;
    int rig=query(x*2+1,mid+1,r,pos,val);
    if(rig != 0)return rig;
    return query(x*2,l,mid,pos,val);
}

pii e[maxn];
int state[maxn];
vector<int> adj[maxn];
void dfs(int u,int par)
{
    static int nTime=0;
    in[u]=++nTime;
    id[nTime]=u;
    for(int c : adj[u])
    {
        if(e[c].first+e[c].second-u != par)
        {
            dfs(e[c].first+e[c].second-u,u);
        }
    }
    out[u]=++nTime;
}
void sol()
{
    cin>>n>>m>>q;
    for(int i=1 ; i<n ; ++i)
    {
        cin>>e[i].first>>e[i].second;
        adj[e[i].first].pb(i);
        adj[e[i].second].pb(i);
    }
    dfs(1,0);
    for(int i=1 ; i<n ; ++i)
    {
        if(in[e[i].first]>in[e[i].second])swap(e[i].first,e[i].second);
    }
    build(1,1,n*2);
    for(int i=1 ; i <= n ; ++i)dp[i]=1;
    while(m--)
    {
        int i;
        cin>>i;
        int v=e[i].second;
        int u=id[query(1,1,n*2,in[e[i].first],in[e[i].first])];
        state[i] ^= 1;
        if(state[i])
        {
            dp[u]+=dp[v]-last[v];
            update(1,1,n*2,in[v],in[v]);
        }
        else
        {
            dp[v]=last[v]=dp[u];
            update(1,1,n*2,in[v],out[v]);
        }
    }
    while(q--)
    {
        int u;
        cin>>u;
//        cerr << in[u] << " ";
//        cerr << query(1 ,1 ,n ,in[u] ,in[u]) << " ";
        cout << dp[id[query(1,1,n*2,in[u],in[u])]] << '\n';
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("PAINT.inp","r",stdin);
//    freopen("PAINT.out","w",stdout);
    int t=1;//cin>>t;
    while (t--)
    {
        sol();
    }
}
/*
*/

Compilation message (stderr)

synchronization.cpp: In function 'void build(long long int, long long int, long long int)':
synchronization.cpp:38:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid=l+r>>1;
      |             ~^~
synchronization.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
synchronization.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid=l+r>>1;
      |             ~^~
synchronization.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
synchronization.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid=l+r>>1;
      |             ~^~

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