제출 #846863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
846863		Ahmed57	Inside information (BOI21_servers)	C++17	0 / 100	67 ms	11800 KiB

servers

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> adj[120001];
array<int,3>P[120001][18][2];
int inf = 1e9;
int hi[120001],stt[120001],enn[120001],tim = 0;
void dfs(int x,int p,int co) {
    hi[x] = hi[p]+1;
    P[x][0][0]={p,co,co};
    P[x][0][1]={p,co,co};
    for(int i = 1;i<=17;i++){
        P[x][i][0] = P[x][i-1][0];
        auto[pr,last,ma]=P[x][i][0];
        if(last<=P[pr][0][0][1]) {
            P[x][i][0]=P[pr][i-1][0];
            P[x][i][0][2]=max(P[x][i][0][2],ma);
        }
    }
    for(int i = 1;i<=17;i++){
        P[x][i][1] = P[x][i-1][1];
        auto[pr,last,ma]=P[x][i][1];
        if(last>=P[pr][0][1][1]) {
            P[x][i][1]=P[pr][i-1][1];
            P[x][i][1][2]=max(P[x][i][1][2],ma);
        }
    }
    stt[x] = tim++;
    for(auto j:adj[x]){
        if(j.first==p)continue;
        dfs(j.first,x,j.second);
    }
    enn[x] = tim;
}
bool ispr(int l, int b){return(stt[l]<=stt[b]&&enn[b]<=enn[l]);}
bool ss = 1 , ind = 0;
int xd(int a,int b,int ty){
    if(!ispr(P[b][17][ty][0],a)){
        ss = 0;return 0;
    }
    if(b==P[b][17][ty][0]||ispr(b,a)) {
        return (ty==1?1:-1)*inf;
    }
    int ma = 0;
    for(int i = 17;i>=0;i--) {
        if(!ispr(P[b][i][ty][0],a)&&!ispr(P[b][i][ty][0],P[b][17][ty][0])) {
            ma=max(ma,P[b][i][ty][2]);
            b=P[b][i][ty][0];
        }
    }
    if(max(ma,P[b][0][ty][2])>ind)ss = 0;
    return P[b][0][ty][1];
}
int main() {
    int n,q;
    cin>>n>>q;
    q+=n-1;
    pair<char,vector<int>> v[q];
    for(int i = 0;i<q;i++){
        cin >> v[i].first;
        if(v[i].first=='S'){
            int a,b;
            cin>>a>>b;
            adj[a].push_back({b,i});
            adj[b].push_back({a,i});
        }else if(v[i].first=='Q'){
            int a,b;
            cin>>a>> b;
            v[i].second={a,b};
        }
    }
    dfs(1,1,0);
    for(int i=0;i<q;i++) {
        if(v[i].first=='S'||v[i].first=='C')continue;
        int a = v[i].second[0], b = v[i].second[1];
        ss = 1;ind = i;
        int a1=xd(0,a,b);
        int a2=xd(1,b,a);
        if(ss&&a1>=a2)cout<<"yes\n";
        else cout<<"no\n";
    }
    return 0;
}

• 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