oj.uz

Submission #863633

# Submission time Handle Problem Language Result Execution time Memory
863633 2023-10-20T16:17:01 Z HossamHero7 Inside information (BOI21_servers) C++14
50 / 100
 267 ms 90604 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 120005;
vector<pair<int,int>> adj[N];
int P[N][30], mn[N][30], mx[N][30], inc[N][30], dcr[N][30];
int dep[N];
void dfs(int node,int par){
    P[node][0] = par;
    for(int k=1;k<30;k++){
        P[node][k] = P[P[node][k-1]][k-1], mn[node][k] = min(mn[node][k-1],mn[P[node][k-1]][k-1]), mx[node][k] = max(mx[node][k-1],mx[P[node][k-1]][k-1]);
        inc[node][k] = inc[node][k-1] && inc[P[node][k-1]][k-1] && (mx[node][k-1] <= mn[P[node][k-1]][k-1]);
        dcr[node][k] = dcr[node][k-1] && dcr[P[node][k-1]][k-1] && (mn[node][k-1] >= mx[P[node][k-1]][k-1]);
    }
    for(auto [ch,c] : adj[node]){
        if(ch == par) continue;
        dep[ch] = dep[node] + 1;
        mn[ch][0] = mx[ch][0] = c;
        inc[ch][0] = dcr[ch][0] = 1;
        dfs(ch,node);
    }
}
int lca(int a,int b){
    if(a == b) return a;
    if(dep[a] < dep[b]) swap(a,b);
    for(int k=29;k>=0;k--){
        if(dep[a] - (1<<k) >= dep[b]) a = P[a][k];
    }
    if(a == b) return a;
    for(int k=29;k>=0;k--){
        if(P[a][k] != P[b][k]){
            a = P[a][k];
            b = P[b][k];
        }
    }
    return P[a][0];
}
int getMx(int a,int b){
    int c = lca(a,b);
    int ret = 0;
    for(int k=29;k>=0;k--) if(dep[a] - (1<<k) >= dep[c]) ret = max(ret,mx[a][k]), a = P[a][k];
    for(int k=29;k>=0;k--) if(dep[b] - (1<<k) >= dep[c]) ret = max(ret,mx[b][k]), b = P[b][k];
    return ret;
}
int getMn(int a,int b){
    int c = lca(a,b);
    int ret = 1e9;
    for(int k=29;k>=0;k--) if(dep[a] - (1<<k) >= dep[c]) ret = min(ret,mx[a][k]), a = P[a][k];
    for(int k=29;k>=0;k--) if(dep[b] - (1<<k) >= dep[c]) ret = min(ret,mx[b][k]), b = P[b][k];
    return ret;
}
bool check(int a,int b){
    int c = lca(a,b);
    int x = 1e9;
    for(int k=29;k>=0;k--){
        if(dep[a] - (1<<k) >= dep[c]) {
            if(!dcr[a][k]) return 0;
            if(mx[a][k] > x) return 0;
            x = mn[a][k]; 
            a = P[a][k];
        }
    }
    int xx = x;
    x = 0;
    for(int k=29;k>=0;k--){
        if(dep[b] - (1<<k) >= dep[c]) {
            if(!inc[b][k]) return 0;
            if(mn[b][k] < x) return 0;
            x = mx[b][k];
            b = P[b][k];
        }
    }
    return (xx>=x);
}
void solve(){
    int n,q;
    cin>>n>>q;
    vector<array<int,3>> qs;
    int cnt = 0;
    for(int qq=0;qq<n+q-1;qq++){
        char c;
        int a,b=0;
        cin>>c>>a;
        if(c != 'C') cin>>b;
        qs.push_back({(int)c,a,b});
        if(c == 'S') {
            adj[a].push_back({b,cnt});
            adj[b].push_back({a,cnt});
        }
        cnt ++;
    }
    dfs(1,0);
    cnt = 0;
    for(auto [c,a,b] : qs){
        if(c == 'S') {cnt ++;continue;}
        if(c == 'Q'){
            if(getMx(a,b) <= cnt && check(a,b)) cout<<"yes"<<endl;
            else cout<<"no"<<endl;
        }
        cnt ++;
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message

servers.cpp: In function 'void dfs(int, int)':
servers.cpp:16:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |     for(auto [ch,c] : adj[node]){
      |              ^
servers.cpp: In function 'void solve()':
servers.cpp:95:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |     for(auto [c,a,b] : qs){
      |              ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8128 KB Output is correct
2 Correct 49 ms 11980 KB Output is correct
3 Correct 54 ms 12120 KB Output is correct
4 Correct 58 ms 11988 KB Output is correct
5 Correct 65 ms 12296 KB Output is correct
6 Correct 64 ms 12008 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8128 KB Output is correct
2 Correct 49 ms 11980 KB Output is correct
3 Correct 54 ms 12120 KB Output is correct
4 Correct 58 ms 11988 KB Output is correct
5 Correct 65 ms 12296 KB Output is correct
6 Correct 64 ms 12008 KB Output is correct
7 Incorrect 38 ms 8128 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 8128 KB Output is correct
2 Correct 179 ms 82432 KB Output is correct
3 Correct 211 ms 81888 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 8128 KB Output is correct
2 Correct 179 ms 82432 KB Output is correct
3 Correct 211 ms 81888 KB Output is correct
4 Incorrect 34 ms 8148 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 34 ms 8204 KB Output is correct
2 Correct 181 ms 90584 KB Output is correct
3 Correct 158 ms 90364 KB Output is correct
4 Correct 227 ms 90552 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8204 KB Output is correct
2 Correct 181 ms 90584 KB Output is correct
3 Correct 158 ms 90364 KB Output is correct
4 Correct 227 ms 90552 KB Output is correct
5 Incorrect 33 ms 8136 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 8136 KB Output is correct
2 Correct 165 ms 82028 KB Output is correct
3 Correct 155 ms 82492 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 8136 KB Output is correct
2 Correct 165 ms 82028 KB Output is correct
3 Correct 155 ms 82492 KB Output is correct
4 Incorrect 38 ms 8132 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8132 KB Output is correct
2 Correct 169 ms 90604 KB Output is correct
3 Correct 175 ms 90496 KB Output is correct
4 Correct 267 ms 90440 KB Output is correct
5 Correct 42 ms 8128 KB Output is correct
6 Correct 177 ms 82044 KB Output is correct
7 Correct 166 ms 82536 KB Output is correct
8 Correct 209 ms 82944 KB Output is correct
9 Correct 172 ms 83008 KB Output is correct
10 Correct 186 ms 87480 KB Output is correct
11 Correct 237 ms 86624 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8132 KB Output is correct
2 Correct 169 ms 90604 KB Output is correct
3 Correct 175 ms 90496 KB Output is correct
4 Correct 267 ms 90440 KB Output is correct
5 Correct 42 ms 8128 KB Output is correct
6 Correct 177 ms 82044 KB Output is correct
7 Correct 166 ms 82536 KB Output is correct
8 Correct 209 ms 82944 KB Output is correct
9 Correct 172 ms 83008 KB Output is correct
10 Correct 186 ms 87480 KB Output is correct
11 Correct 237 ms 86624 KB Output is correct
12 Incorrect 35 ms 8132 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8132 KB Output is correct
2 Correct 45 ms 11984 KB Output is correct
3 Correct 50 ms 12036 KB Output is correct
4 Correct 58 ms 11904 KB Output is correct
5 Correct 66 ms 12316 KB Output is correct
6 Correct 50 ms 12008 KB Output is correct
7 Correct 34 ms 8144 KB Output is correct
8 Correct 175 ms 82008 KB Output is correct
9 Correct 174 ms 81920 KB Output is correct
10 Correct 33 ms 8144 KB Output is correct
11 Correct 166 ms 90396 KB Output is correct
12 Correct 179 ms 90380 KB Output is correct
13 Correct 216 ms 90488 KB Output is correct
14 Correct 35 ms 8136 KB Output is correct
15 Correct 170 ms 82072 KB Output is correct
16 Correct 150 ms 82424 KB Output is correct
17 Correct 203 ms 82944 KB Output is correct
18 Correct 185 ms 82852 KB Output is correct
19 Correct 192 ms 87252 KB Output is correct
20 Correct 252 ms 86528 KB Output is correct
21 Correct 177 ms 81916 KB Output is correct
22 Correct 181 ms 82044 KB Output is correct
23 Correct 182 ms 82376 KB Output is correct
24 Correct 185 ms 82424 KB Output is correct
25 Correct 197 ms 84164 KB Output is correct
26 Correct 145 ms 81916 KB Output is correct
27 Correct 162 ms 81724 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8132 KB Output is correct
2 Correct 45 ms 11984 KB Output is correct
3 Correct 50 ms 12036 KB Output is correct
4 Correct 58 ms 11904 KB Output is correct
5 Correct 66 ms 12316 KB Output is correct
6 Correct 50 ms 12008 KB Output is correct
7 Correct 34 ms 8144 KB Output is correct
8 Correct 175 ms 82008 KB Output is correct
9 Correct 174 ms 81920 KB Output is correct
10 Correct 33 ms 8144 KB Output is correct
11 Correct 166 ms 90396 KB Output is correct
12 Correct 179 ms 90380 KB Output is correct
13 Correct 216 ms 90488 KB Output is correct
14 Correct 35 ms 8136 KB Output is correct
15 Correct 170 ms 82072 KB Output is correct
16 Correct 150 ms 82424 KB Output is correct
17 Correct 203 ms 82944 KB Output is correct
18 Correct 185 ms 82852 KB Output is correct
19 Correct 192 ms 87252 KB Output is correct
20 Correct 252 ms 86528 KB Output is correct
21 Correct 177 ms 81916 KB Output is correct
22 Correct 181 ms 82044 KB Output is correct
23 Correct 182 ms 82376 KB Output is correct
24 Correct 185 ms 82424 KB Output is correct
25 Correct 197 ms 84164 KB Output is correct
26 Correct 145 ms 81916 KB Output is correct
27 Correct 162 ms 81724 KB Output is correct
28 Incorrect 35 ms 8020 KB Extra information in the output file
29 Halted 0 ms 0 KB -