Submission #398913

#	Time	Username	Problem	Language	Result	Execution time	Memory
398913		REALITYNB	Inside information (BOI21_servers)	C++14	0 / 100	92 ms	85740 KiB

servers

#include <bits/stdc++.h> 
#define pii pair<int,int> 
#define F first 
#define S second 
#define mp make_pair 
#define NO "no"
#define YES "yes" 
using namespace std; 
const int mxn = 3e5+1 , lg =20 ; 
vector<pii> adj[mxn] ; 
int tim = 0 ; 
vector<int> in(mxn) , out(mxn) , lvl(mxn,-1) , le(mxn,-1) ; 
vector<vector<int>> anc(lg,vector<int>(mxn,-1)) , inc(lg,vector<int>(mxn,-1)) , decr(lg,vector<int>(mxn,-1))  ;  
int find(int a , int dis){
    for(int i=0;i<lg;i++){
        if((1<<i)&dis){
            a=anc[i][a];
            if(a==-1) break ; 
        }
    }
    return a ; 
}
void dfs(int a ,int p,int l,int lastedge){
    in[a]=++tim ; 
    lvl[a]=l; 
    anc[0][a]=p; 
    le[a]=lastedge ; 
    for(int i=1;i<lg;i++){
        if(anc[i-1][a]==-1) continue ; 
        anc[i][a]=anc[i-1][anc[i-1][a]] ; 
    }
    inc[0][a]=decr[0][a]=lastedge ; 
    for(int i=1;i<lg;i++){
        int na = find(a,(1<<(i-1)-1)) ; 
        int nb = find(a,(1<<(i-1))) ; 
        if(na==-1) continue ; 
        if(nb==-1) continue ; 
        if((le[nb]==-1||le[na]<le[nb])&&inc[i-1][a]!=-1&&inc[i-1][nb]!=-1) inc[i][a]=inc[i-1][nb];
        else inc[i][a]=-1 ; 
    }   
    for(int i=1;i<lg;i++){
        int na = find(a,(1<<(i-1))-1) ; 
        int nb = find(a,(1<<(i-1))) ; 
        if(na==-1) continue ; 
        if(nb==-1) continue ; 
        if((le[nb]==-1||le[na]>le[nb])&&decr[i-1][a]!=-1&&decr[i-1][nb]!=-1) decr[i][a]=decr[i-1][a];
        else decr[i][a]=-1 ; 
    }   
    for(pii x : adj[a]){
        if(x.F==p) continue ; 
        dfs(x.F,a,l+1,x.S); 
    }
    out[a]=++tim; 
}
int lca(int a, int b){
    if(in[a]<=out[b]&&out[b]<=out[a]) return a ; 
    if(in[b]<=out[a]&&out[a]<=out[b]) return b ;
    for(int i=lg-1;i>-1;i--){
        if(anc[i][a]||in[anc[i][a]]<=in[b]&&out[b]<=out[anc[i][a]]) continue; 
        a =anc[i][a] ; 
    }
    return anc[0][a] ;
}
int is_inc(int a, int lvl){
    int ans = 0 ;
    for(int i=0;i<lg;i++){
        if((1<<i)&lvl){
            if(inc[i][a]==-1) return -1 ; 
            int ba = a ; 
            a=anc[i][a] ; 
            if(ans>le[a]) return -1 ;  
            ans=le[find(ba,(1<<i)-1)];

        }
    } 
    return ans ; 
}
int is_decr(int a, int lvl){
    int ans = 1e9;
    int mn = 0 ; 
    if(lvl!=0) mn=le[a] ; 
   /* cout << a << " : {" ; 
    cout << endl ; 
    for(int i=0;i<lg;i++){
        cout << i << " " << decr[i][a] << endl ; 
    }
    cout << "}" ; 
    cout << lvl << "x"; */
    for(int i=0;i<lg;i++){
        if((1<<i)&lvl){
            if(decr[i][a]==-1)
     //           cout << "deed" << a << endl ; 
       //         cout<< endl <<  a << " " << "deded" <<  decr[i-1][a] << endl ; 
               return -1 ; 

            int ba = a ; 
            a=anc[i][a] ; 
            if(ans<le[a]){
                return -1 ;  
            }
            ans=le[find(ba,(1<<i)-1)];

        }
    } 
   // cout <<"answer " << ans << endl ; 
    return mn ; 
}
int main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(nullptr); 

    int n ,q ; 
    cin>>n>>q ; 
    int k = n-1+q ; 
    vector<int> u , v ,t ; 
    int tim = 0 ; 
    while(k--){
        ++tim; 
        char x ; 
        cin>>x ; 
        int a,b ; 
        cin>>a>>b ; 
        if(x=='S'){
            adj[a].push_back(mp(b,tim)); 
            adj[b].push_back(mp(a,tim)) ; 
        }
        else{
            u.push_back(a) ; 
            v.push_back(b) ; 
            t.push_back(tim) ; 
        }
    }  
    dfs(1,-1,0,-1) ; 
    for(int i=0;i<u.size();i++){
        int a = u[i],b = v[i],ti =t[i] ; 
        int lc = lca(a,b) ; 
        int pathb = is_inc(b,lvl[b]-lvl[lc]); 
        int patha=is_decr(a,lvl[a]-lvl[lc]) ;
        //cout << a <<  " " << b << endl ;  
        //cout <<patha << " " << pathb<< " " << lc << endl  ; 
        if(lc==a){
            if(pathb!=-1&&pathb<ti){
                cout << YES ; 
            }
            else cout << NO ; 
        }
        else if(lc==b){
            if(patha!=-1&&patha<ti) cout << YES ; 
            else cout << NO ; 
        }
        else{
            if(patha==-1||pathb==-1) cout << NO    ; 
            else if(le[find(a,lvl[a]-lvl[lc]-1)]>le[find(b,lvl[b]-lvl[lc]-1)]) cout << YES ; 
            else if(max(patha,pathb)<ti)cout << NO ; 
            else cout << YES ; 
        }
        cout << '\n' ; 
    }
    return 0 ; 
}

Compilation message (stderr)

servers.cpp: In function 'void dfs(int, int, int, int)':
servers.cpp:34:34: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   34 |         int na = find(a,(1<<(i-1)-1)) ;
      |                             ~~~~~^~
servers.cpp: In function 'int lca(int, int)':
servers.cpp:59:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   59 |         if(anc[i][a]||in[anc[i][a]]<=in[b]&&out[b]<=out[anc[i][a]]) continue;
servers.cpp: In function 'int main()':
servers.cpp:134:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for(int i=0;i<u.size();i++){
      |                 ~^~~~~~~~~

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5