oj.uz

Submission #883979

# Submission time Handle Problem Language Result Execution time Memory
883979 2023-12-06T13:43:46 Z 8pete8 Synchronization (JOI13_synchronization) C++17
100 / 100
 1202 ms 63684 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
const int mod=1e9+7,mxn=2e5+5,lg=30,inf=1e18,minf=-1e18;
vector<pii>e,adj[mxn+10];
int hvy[mxn+10],pos[mxn+10],h[mxn+10],up[mxn+10][lg+10],sz[mxn+10],hvypa[mxn+10];
int last[mxn+10],mx[mxn+10],pa[mxn+10];
bitset<mxn+10>on;
int n;
int checktimer=0;
bitset<mxn+10>vis;
void dfs(int cur,int p){
    if(vis[cur])return;
    vis[cur]=true;
    for(auto i:adj[cur]){
        if(i.f==p)continue;
        h[i.f]=h[cur]+1;
        up[i.f][0]=cur;
        dfs(i.f,cur);
        sz[cur]+=sz[i.f];
    }
    sz[cur]++;
}
int cnt=1;
void hld(int cur,int p,int phvy){
    if(vis[cur])return;
    vis[cur]=true;
    pos[cur]=cnt++;
    hvypa[cur]=phvy;
    for(auto i:adj[cur])if(i.f!=p&&sz[hvy[cur]]<sz[i.f])hvy[cur]=i.f;
    if(hvy[cur])hld(hvy[cur],cur,phvy);
    for(auto i:adj[cur])if(i.f!=p&&i.f!=hvy[cur])hld(i.f,cur,i.f);
}
struct seg{
    bool v[2*mxn+10];
    void init(){for(int i=0;i<=2*mxn+5;i++)v[i]=false;}
    void update(int pos,bool val){
        pos+=n+1;
        v[pos]=val;
        for(;pos>0;pos>>=1)v[pos>>1]=(v[pos]&v[pos^1]);
    }
    bool qry(int l,int r){
        bool ans=true;
        for(l+=n+1,r+=n+1;l<=r;l>>=1,r>>=1){
            if(l&1)ans&=(v[l++]);
            if(!(r&1))ans&=(v[r--]);
        }
        return ans;
    }
}t;
struct fen{
    int fwk[mxn+10];
    void init(){for(int i=0;i<=mxn+5;i++)fwk[i]=0;}
    void update(int pos,int val){for(int i=pos;i<=n;i+=(i&-i))fwk[i]+=val;}
    int qry(int pos){
        int sum=0;
        for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
        return sum;
    }
}f;

void upd(int st,int above,int val){
    int cur=st;
    checktimer=0;
    while(hvypa[cur]!=hvypa[above]){
        checktimer++;
        f.update(pos[cur]+1,-val);
        f.update(pos[hvypa[cur]],val);
        cur=up[hvypa[cur]][0];
        if(checktimer>40)assert(0);
    }
    f.update(pos[cur]+1,-val);
    f.update(pos[above],val);
}
int check2=0;
int check(int st,int m){
    bool ans=true;
    int cur=st,above=st;
    checktimer=0;
    for(int i=0;i<=lg;i++)if(m&(1<<i))above=up[above][i];
    while(hvypa[cur]!=hvypa[above]){
        checktimer++;
        ans&=t.qry(pos[hvypa[cur]],pos[cur]);
        cur=up[hvypa[cur]][0];
        if(checktimer>40)assert(0);
    }
    ans&=t.qry(pos[above],pos[cur]);
    if(ans)return above;
    return 0;
}
int findpa(int cur){
    check2=0;
    int l=0,r=h[cur],ans=minf;
    while(l<=r){
        check2++;
        int mid=(l+r)/2;
        int g=check(cur,mid);
        if(check2>40)assert(0);
        if(g){
            l=mid+1;
            if(ans==minf||h[ans]>h[g])ans=g;
        }
        else r=mid-1;
    }
    return (ans==minf?cur:ans);
}
int cmx=minf;
int find(int a){
    if(pa[a]==a)return pa[a];
    checktimer++;
    if(on[a]){
        if(pa[a]==0)pa[a]=up[a][0];
        pa[a]=find(pa[a]);
        mx[a]=max(mx[a],pa[a]);
    }
    else pa[a]=a;
    return pa[a];
}
void findans(int cur,int p){
    if(!on[cur])cmx=max(mx[cur],f.qry(pos[cur]));
    else cmx=max({cmx,mx[cur],f.qry(pos[cur])});
    mx[cur]=cmx;
    for(auto i:adj[cur])if(i.f!=p)findans(i.f,cur);
}
int32_t main(){
	fastio
    int q,m;cin>>n>>q>>m;
    for(int i=1;i<=n-1;i++){
        int a,b;cin>>a>>b;
        e.pb({a,b});
        adj[a].pb({b,i});
        adj[b].pb({a,i});
    }
    dfs(1,-1);
    vis.reset();
    hld(1,-1,1);
    vis.reset();
    f.init();
    t.init();
    for(int i=1;i<=lg;i++)up[1][i]=1;
    for(int j=1;j<=lg;j++)for(int i=2;i<=n;i++)up[i][j]=up[up[i][j-1]][j-1];
    f.update(1,1);
    while(q--){
        int a;cin>>a;
        a--;
        if(h[e[a].f]<h[e[a].s])a=e[a].s;
        else a=e[a].f;
        if(on[a]){
            int node=up[findpa(a)][0];
            last[a]=f.qry(pos[a]);
            mx[node]=max(mx[node],f.qry(pos[node]));
            mx[a]=max(mx[a],mx[node]);
            t.update(pos[a],false);
        }
        else{
            t.update(pos[a],true);
            int node=up[findpa(a)][0];
            int tmp=f.qry(pos[a])-last[a];
            mx[node]=max(mx[node],f.qry(pos[node]));
            upd(up[a][0],node,tmp);
            mx[node]=max(mx[node],mx[node]+(tmp));
        }
        on[a]=!on[a];
    }
    findans(1,-1);
    int checktimer=0;
    for(int i=1;i<=m;i++){
        int a;cin>>a;
        if(!vis[a])cout<<mx[find(a)]<<'\n';
        else cout<<mx[a]<<'\n';
    }
	return 0;
}

Compilation message

synchronization.cpp: In function 'int32_t main()':
synchronization.cpp:197:9: warning: unused variable 'checktimer' [-Wunused-variable]
  197 |     int checktimer=0;
      |         ^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12376 KB Output is correct
2 Correct 3 ms 12376 KB Output is correct
3 Correct 3 ms 12380 KB Output is correct
4 Correct 2 ms 12380 KB Output is correct
5 Correct 4 ms 12380 KB Output is correct
6 Correct 4 ms 12632 KB Output is correct
7 Correct 16 ms 17620 KB Output is correct
8 Correct 15 ms 17624 KB Output is correct
9 Correct 17 ms 17624 KB Output is correct
10 Correct 197 ms 53580 KB Output is correct
11 Correct 288 ms 53696 KB Output is correct
12 Correct 1053 ms 61060 KB Output is correct
13 Correct 101 ms 52744 KB Output is correct
14 Correct 205 ms 52928 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 56256 KB Output is correct
2 Correct 234 ms 56092 KB Output is correct
3 Correct 273 ms 60352 KB Output is correct
4 Correct 265 ms 60096 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Correct 3 ms 12380 KB Output is correct
3 Correct 3 ms 12380 KB Output is correct
4 Correct 3 ms 12376 KB Output is correct
5 Correct 4 ms 12376 KB Output is correct
6 Correct 5 ms 12752 KB Output is correct
7 Correct 34 ms 18484 KB Output is correct
8 Correct 1182 ms 61888 KB Output is correct
9 Correct 1078 ms 61832 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 61828 KB Output is correct
2 Correct 274 ms 61188 KB Output is correct
3 Correct 278 ms 61412 KB Output is correct
4 Correct 271 ms 61372 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12376 KB Output is correct
2 Correct 3 ms 12380 KB Output is correct
3 Correct 3 ms 12380 KB Output is correct
4 Correct 3 ms 12464 KB Output is correct
5 Correct 4 ms 12636 KB Output is correct
6 Correct 21 ms 17624 KB Output is correct
7 Correct 309 ms 54444 KB Output is correct
8 Correct 1202 ms 62052 KB Output is correct
9 Correct 162 ms 53764 KB Output is correct
10 Correct 201 ms 53976 KB Output is correct
11 Correct 270 ms 57532 KB Output is correct
12 Correct 254 ms 59944 KB Output is correct
13 Correct 303 ms 63684 KB Output is correct