oj.uz

Submission #883939

# Submission time Handle Problem Language Result Execution time Memory
883939 2023-12-06T13:07:24 Z 8pete8 Synchronization (JOI13_synchronization) C++17
30 / 100
 860 ms 62656 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#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];
bitset<mxn+10>on;
int n;
void dfs(int cur,int p){
    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){
    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 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 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;
    while(hvypa[cur]!=hvypa[above]){
        f.update(pos[cur]+1,-val);
        f.update(pos[hvypa[cur]],val);
        cur=up[hvypa[cur]][0];
    }
    f.update(pos[cur]+1,-val);
    f.update(pos[above],val);
}
int check(int st,int m){
    bool ans=true;
    int cur=st,above=st;
    for(int i=0;i<=lg;i++)if(m&(1<<i))above=up[above][i];
    while(hvypa[cur]!=hvypa[above]){
        ans&=t.qry(pos[hvypa[cur]],pos[cur]);
        cur=up[hvypa[cur]][0];
    }
    ans&=t.qry(pos[above],pos[cur]);
    if(ans)return above;
    return 0;
}
int findpa(int cur){
    int l=0,r=h[cur],ans=minf;
    while(l<=r){
        int mid=(l+r)/2;
        int g=check(cur,mid);
        if(g){
            l=mid+1;
            if(ans==minf||h[ans]>h[g])ans=g;
        }
        else r=mid-1;
    }
    return (ans==minf?cur:ans);
}
int ans=minf;
void findans(int cur,int p){
    if(!on[cur])ans=max(mx[cur],f.qry(pos[cur]));
    else ans=max({ans,mx[cur],f.qry(pos[cur])});
    mx[cur]=ans;
    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);
    hld(1,-1,1);
    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);
    for(int i=1;i<=m;i++){
        int a;cin>>a;
        cout<<mx[a]<<'\n';
    }
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14780 KB Output is correct
5 Incorrect 3 ms 14680 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 233 ms 58908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 5 ms 16988 KB Output is correct
7 Correct 32 ms 20508 KB Output is correct
8 Correct 822 ms 62468 KB Output is correct
9 Correct 860 ms 62476 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 62656 KB Output is correct
2 Correct 257 ms 62172 KB Output is correct
3 Correct 266 ms 62560 KB Output is correct
4 Correct 253 ms 62236 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Incorrect 2 ms 14684 KB Output isn't correct
4 Halted 0 ms 0 KB -