oj.uz

답안 #846867

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
846867 2023-09-08T14:46:29 Z Ahmed57 Inside information (BOI21_servers) C++17
0 / 100
 56 ms 11744 KB 
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> adj[120001];
array<int,3>P[120001][18][2];
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 lca(int a,int b,int t) {
    int ss = 1 , vv = 0;
    if(ispr(P[a][17][ss][0],a)&&ispr(P[a][17][ss][0],b)&&ispr(P[b][17][vv][0],a)&&ispr(P[b][17][vv][0],b)){

    }else{
        return 0;
    }
    if(hi[a]<hi[b]){swap(a,b);swap(ss,vv);}
    int ma = -1;
    for(int i = 17;i>=0;i--){
        if(hi[a]-(1<<i)>=hi[b]){
            ma = max(ma,P[a][i][ss][2]);
            a = P[a][i][ss][0];
        }
    }
    if(a==b)return (ma<t);
    for(int i = 17;i>=0;i--){
        if(P[a][i][ss][0]!=P[b][i][vv][0]){
            ma = max({ma,P[a][i][ss][2],P[b][i][vv][2]});
            a = P[a][i][ss][0];
            b = P[b][i][vv][0];
        }
    }
    return ((max({ma,P[a][0][ss][2],P[b][0][vv][2]})<t)&&(P[a][0][ss][1]>P[b][0][vv][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};
        }else{
            int a;
            cin>>a;
        }
    }
    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];
        if(lca(b,a,i)){
            cout<<"yes\n";
        }else{
            cout<<"no\n";
        }
    }
    return 0;
}

Subtask #1
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 11744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 11744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 11644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 11644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -