제출 #863633

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
863633		HossamHero7	Inside information (BOI21_servers)	C++14	50 / 100	267 ms	90604 KiB

servers

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5