oj.uz

Submission #846844

# Submission time Handle Problem Language Result Execution time Memory
846844 2023-09-08T14:14:53 Z Ahmed57 Inside information (BOI21_servers) C++17
7.5 / 100
 229 ms 76372 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(hi[a]!=hi[b])return 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];
        }
    }
    if(P[a][0][ss][0]!=P[b][0][vv][0]||hi[a]!=hi[b])return 0;
    return (max({ma,P[a][0][ss][2],P[b][0][vv][2]})<t)&&(P[a][0][ss][2]>P[b][0][vv][2]);
}
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(a,b,i)){
            cout<<"yes\n";
        }else{
            cout<<"no\n";
        }
    }
    return 0;
}

Subtask #1
0 / 2.5

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

Subtask #2
0 / 2.5

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

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 11604 KB Output is correct
2 Correct 205 ms 71620 KB Output is correct
3 Correct 215 ms 71620 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 11604 KB Output is correct
2 Correct 205 ms 71620 KB Output is correct
3 Correct 215 ms 71620 KB Output is correct
4 Incorrect 68 ms 11348 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 11604 KB Output is correct
2 Correct 198 ms 76344 KB Output is correct
3 Correct 212 ms 76244 KB Output is correct
4 Correct 229 ms 76372 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 11604 KB Output is correct
2 Correct 198 ms 76344 KB Output is correct
3 Correct 212 ms 76244 KB Output is correct
4 Correct 229 ms 76372 KB Output is correct
5 Incorrect 47 ms 11312 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 11612 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 11612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 11604 KB Output is correct
2 Correct 199 ms 76316 KB Output is correct
3 Correct 194 ms 76372 KB Output is correct
4 Correct 228 ms 76348 KB Output is correct
5 Incorrect 50 ms 11600 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 11604 KB Output is correct
2 Correct 199 ms 76316 KB Output is correct
3 Correct 194 ms 76372 KB Output is correct
4 Correct 228 ms 76348 KB Output is correct
5 Incorrect 50 ms 11600 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 50 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 50 ms 11600 KB Output isn't correct
2 Halted 0 ms 0 KB -