oj.uz

Submission #883974

# Submission time Handle Problem Language Result Execution time Memory
883974 2023-12-06T13:41:13 Z 8pete8 Synchronization (JOI13_synchronization) C++17
30 / 100
 1059 ms 121604 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(checktimer>=2*n)assert(0);
    if(on[a]){
        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:198:9: warning: unused variable 'checktimer' [-Wunused-variable]
  198 |     int checktimer=0;
      |         ^~~~~~~~~~

Subtask #1
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 12380 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 17 ms 17608 KB Output is correct
8 Correct 18 ms 17620 KB Output is correct
9 Correct 17 ms 17620 KB Output is correct
10 Correct 211 ms 53440 KB Output is correct
11 Correct 233 ms 53700 KB Output is correct
12 Correct 879 ms 61060 KB Output is correct
13 Correct 169 ms 52656 KB Output is correct
14 Correct 151 ms 52924 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 56188 KB Output is correct
2 Correct 236 ms 56136 KB Output is correct
3 Correct 273 ms 60116 KB Output is correct
4 Correct 267 ms 60308 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Correct 3 ms 12376 KB Output is correct
3 Correct 4 ms 12376 KB Output is correct
4 Correct 3 ms 12380 KB Output is correct
5 Runtime error 18 ms 25056 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 61828 KB Output is correct
2 Runtime error 330 ms 121604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 3 ms 12380 KB Output is correct
4 Correct 3 ms 12380 KB Output is correct
5 Correct 4 ms 12636 KB Output is correct
6 Correct 17 ms 17756 KB Output is correct
7 Correct 229 ms 54484 KB Output is correct
8 Correct 1059 ms 61792 KB Output is correct
9 Correct 114 ms 53724 KB Output is correct
10 Runtime error 191 ms 107964 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -