제출 #601146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601146		alexander707070	Inside information (BOI21_servers)	C++14	50 / 100	564 ms	37700 KiB

servers

#include<bits/stdc++.h>
#define MAXN 400007
using namespace std;

struct node{
    bool ok;
    int l,r;
};

int n,q,a[MAXN],b[MAXN],num;
char type[MAXN];
vector<int> v[MAXN];
int sz[MAXN],heavy[MAXN],head[MAXN];
int pos[MAXN],dep[MAXN],parent[MAXN];

void dfs(int x,int p,int dd){
    sz[x]=1; dep[x]=dd; parent[x]=p;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p)continue;
        dfs(v[x][i],x,dd+1);
        if(sz[v[x][i]]>sz[heavy[x]]){
            heavy[x]=v[x][i];
        }
        sz[x]+=sz[v[x][i]];
    }
}

void decompose(int x,int p,int h){
    if(x==0)return;
    num++; pos[x]=num; head[x]=h;

    decompose(heavy[x],x,h);
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p or v[x][i]==heavy[x])continue;
        decompose(v[x][i],x,v[x][i]);
    }
}

node tree[2][4*MAXN];

node combine(int dir,node fr,node sc){
    if(fr.l==-1)return sc;
    if(sc.l==-1)return fr;
    if(dir==0){
        if(fr.ok and sc.ok and fr.r<sc.l){
            return {true,fr.l,sc.r};
        }else{
            return {false,fr.l,sc.r};
        }
    }else{
        if(fr.ok and sc.ok and fr.r>sc.l){
            return {true,fr.l,sc.r};
        }else{
            return {false,fr.l,sc.r};
        }
    }
}

void update(int dir,int v,int l,int r,int pos,int val){
    if(l==r){
        tree[dir][v]={true,val,val};
    }else{
        int tt=(l+r)/2;
        if(pos<=tt)update(dir,2*v,l,tt,pos,val);
        else update(dir,2*v+1,tt+1,r,pos,val);
        tree[dir][v]=combine(dir,tree[dir][2*v],tree[dir][2*v+1]);
    }
}

node getval(int dir,int v,int l,int r,int ll,int rr){
    if(ll>rr){
        if(dir==0)return {true,-1,-1};
        else return {true,-1,-1};
    }
    if(l==ll and r==rr){
        return tree[dir][v];
    }else{
        int tt=(l+r)/2;
        return combine( dir, getval(dir,2*v,l,tt,ll,min(tt,rr)) , getval(dir,2*v+1,tt+1,r,max(tt+1,ll),rr) );
    }
}

bool query(int a,int b){
    node lt={true,-1,-1},rt={true,-1,-1};
    while(head[a]!=head[b]){
        if(dep[head[a]]>dep[head[b]]){
            lt=combine(1,getval(1,1,1,n,pos[head[a]],pos[a]),lt);
            a=parent[head[a]];
        }else{
            rt=combine(0,getval(0,1,1,n,pos[head[b]],pos[b]),rt);
            b=parent[head[b]];
        }
    }
    if(dep[a]<dep[b]){
        rt=combine(0,getval(0,1,1,n,pos[a]+1,pos[b]),rt);
    }else{
        lt=combine(1,getval(1,1,1,n,pos[b]+1,pos[a]),lt);
    }
    swap(lt.l,lt.r);
    return combine(0,lt,rt).ok;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>q;
    for(int i=1;i<=n+q-1;i++){
        cin>>type[i];
        if(type[i]=='S'){
            cin>>a[i]>>b[i];
            v[a[i]].push_back(b[i]);
            v[b[i]].push_back(a[i]);
        }else if(type[i]=='Q'){
            cin>>a[i]>>b[i];
        }else{
            cin>>a[i];
        }
    }

    dfs(1,0,1);
    decompose(1,0,1);

    num=0;
    for(int i=1;i<=n+q-1;i++){
        if(type[i]=='S'){
            num++;
            if(dep[a[i]]>dep[b[i]])swap(a[i],b[i]);
            update(0,1,1,n,pos[b[i]],num);
            update(1,1,1,n,pos[b[i]],num);  
        }else if(type[i]=='Q'){
            if(query(b[i],a[i])){
                cout<<"yes\n";
            }else{
                cout<<"no\n";
            }
        }else{
            cout<<0<<"\n";
        }
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

servers.cpp: In function 'void dfs(int, int, int)':
servers.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
servers.cpp: In function 'void decompose(int, int, int)':
servers.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~

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