Submission #1122930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122930		Newtonabc	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	13 ms	14664 KiB

bitaro

#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=1e5+10;
vector<int> adj[N],rev[N],g[N];
vector<int> com[N];
priority_queue<pair<pair<int,int>,int>> pq;
bool vs[N];
queue<int> q;
int cnt,type[N],root[N],dep[N],nidx[N],t,in[N],out[N],sz[N];
void bfscompo(int u){
    q.push(u);
    vs[u]=true;
    com[cnt].push_back(u);
    type[u]=cnt;
    root[cnt]=max(root[cnt],u);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<adj[u].size();i++){
            int v=adj[u][i];
            if(vs[v]) continue;
            vs[v]=true;
            com[cnt].push_back(v);
            type[v]=cnt;
            root[cnt]=max(root[cnt],v);
            q.push(v);
        }
    }
}
struct segment_tree{
    vector<int> s,arr;
    void init(int n){
        s.resize(4*n+10);
        arr.resize(n+10);
    }
    void build(int l,int r,int idx){
        if(l==r){
            s[idx]=arr[l];
            return;
        }
        int m=(l+r)/2;
        build(l,m,idx*2);
        build(m+1,r,idx*2+1);
        s[idx]=max(s[idx*2],s[idx*2+1]);
    }
    void update(int l,int r,int idx,int a,int b){
        if(a>r || a<l) return;
        if(l==r){
            s[idx]=b;
            return;
        }
        int m=(l+r)/2;
        update(l,m,idx*2,a,b);
        update(m+1,r,idx*2+1,a,b);
        s[idx]=max(s[idx*2],s[idx*2+1]);
    }
    int query(int l,int r,int idx,int a,int b){
        if(a>r || b<l) return INT_MIN;
        if(a<=l && b>=r) return s[idx];
        int m=(l+r)/2;
        return max(query(l,m,idx*2,a,b),query(m+1,r,idx*2+1,a,b));
    }
}tree[N];
void dfs(int u,int p,int num){
    in[u]=++t;
    tree[num].arr[t]=dep[u];
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v==p) continue;
        dfs(v,u,num);
    }
    out[u]=t;
}
int main(){
    int n,m,l;
    cin>>n >>m >>l;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u >>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if(vs[i]) continue;
        cnt++;
        bfscompo(i);
    }
    for(int i=1;i<=n;i++) vs[i]=false;
    for(int i=1;i<=cnt;i++){
        pq.push(mp(mp(root[i],0),root[i]));
        while(!pq.empty()){
            int u=pq.top().first.first;
            int d=pq.top().first.second;
            int pre=pq.top().second;
            pq.pop();
            if(vs[u]) continue;
            vs[u]=true;
            g[u].push_back(pre);
            g[pre].push_back(u);
            dep[u]=d;
            for(int i=0;i<adj[u].size();i++){
                int v=adj[u][i];
                if(vs[v]) continue;
                pq.push(mp(mp(v,d+1),u));
            }
        }
    }
    //for(int i=1;i<=n;i++) cout<<dep[i] <<" ";
    for(int i=1;i<=cnt;i++){
        t=0,tree[i].init((int)com[i].size());
        dfs(root[i],root[i],i);
        sz[i]=t;
        tree[i].build(1,t,1);
    }
    /*for(int i=1;i<=n;i++) cout<<in[i] <<" ";
    cout<<"\n";
    for(int i=1;i<=n;i++) cout<<out[i] <<" ";*/
    //cout<<tree[1].arr.size() <<" " <<tree[1].s.size();
    //for(int i=1;i<=n;i++) cout<<dep[i] <<" ";
    queue<pair<int,int> > tmp;
    
    while(l--){
        int a,b;
        cin>>a >>b;
        for(int i=0;i<b;i++){
            int inp;
            cin>>inp;
            tmp.push(mp(type[inp],in[inp]));
            tree[type[inp]].update(1,sz[type[inp]],1,in[inp],-1);
        }
        int ans=tree[type[a]].query(1,sz[type[a]],1,in[a],out[a]);
        if(ans<0) cout<<-1;
        else cout<<ans-dep[a];
        cout<<"\n";
        while(!tmp.empty()){
            int fa=tmp.front().first;
            int fb=tmp.front().second;
            tmp.pop();
            tree[fa].update(1,sz[fa],1,fb,tree[fa].arr[fb]);
        }
    }
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86