oj.uz

Submission #846863

# Submission time Handle Problem Language Result Execution time Memory
846863 2023-09-08T14:39:37 Z Ahmed57 Inside information (BOI21_servers) C++17
0 / 100
 67 ms 11800 KB 
#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

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 11800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 11800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -