oj.uz

Submission #1008621

# Submission time Handle Problem Language Result Execution time Memory
1008621 2024-06-26T15:52:25 Z vjudge1 Synchronization (JOI13_synchronization) C++17
100 / 100
 131 ms 25488 KB 

#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2688 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 11 ms 4444 KB Output is correct
8 Correct 12 ms 4444 KB Output is correct
9 Correct 10 ms 4444 KB Output is correct
10 Correct 118 ms 19996 KB Output is correct
11 Correct 111 ms 19792 KB Output is correct
12 Correct 120 ms 24660 KB Output is correct
13 Correct 73 ms 19648 KB Output is correct
14 Correct 66 ms 18564 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 21564 KB Output is correct
2 Correct 54 ms 21364 KB Output is correct
3 Correct 47 ms 23376 KB Output is correct
4 Correct 44 ms 23324 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2720 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 9 ms 5168 KB Output is correct
8 Correct 100 ms 25452 KB Output is correct
9 Correct 127 ms 25488 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 25424 KB Output is correct
2 Correct 68 ms 24660 KB Output is correct
3 Correct 65 ms 24712 KB Output is correct
4 Correct 68 ms 24660 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2904 KB Output is correct
6 Correct 10 ms 4700 KB Output is correct
7 Correct 131 ms 20748 KB Output is correct
8 Correct 102 ms 25424 KB Output is correct
9 Correct 92 ms 20872 KB Output is correct
10 Correct 98 ms 19796 KB Output is correct
11 Correct 84 ms 22752 KB Output is correct
12 Correct 73 ms 22732 KB Output is correct
13 Correct 63 ms 24660 KB Output is correct