제출 #895329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895329		TahirAliyev	Inside information (BOI21_servers)	C++17	50 / 100	305 ms	33948 KiB

servers

#include <bits/stdc++.h>

#define ll long long
#define oo 1e9
#define pii pair<int, int>

using namespace std;

const int MAX = 12e4 + 4, LOGMAX = 18;
int n, m;
int par[LOGMAX][MAX];
int tin[MAX], tout[MAX];
int h[MAX];
vector<pii> g[MAX];
int dp[MAX][2];
int parl[MAX];

int t = 1;
void dfs(int node, int p){
    par[0][node] = p;
    tin[node] = t++;
    for(pii to : g[node]){
        if(p == to.first) continue;
        h[to.first] = h[node] + 1;
        dp[to.first][0] = node;
        dp[to.first][1] = node;
        if((parl[node] > to.second) || !parl[node]){
            dp[to.first][0] = dp[node][0];
        }
        if((parl[node] < to.second) || !parl[node]){
            dp[to.first][1] = dp[node][1];
        }
        parl[to.first] = to.second; 
        dfs(to.first, node);
    }
    tout[node] = t++;
}

bool isAnc(int u, int v){
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}

int lift(int u, int l){
    for(int j = LOGMAX - 1; j >= 0; j--){
        if(!isAnc(par[j][u], l)) u = par[j][u];
    }
    return u;
}
int lca(int u, int v){
    if(isAnc(u, v)) return u;
    if(isAnc(v, u)) return v;  
    return par[0][lift(u, v)];
}

int dsu[MAX];

int f(int node){
    if(dsu[node] < 0) return node;
    return dsu[node] = f(dsu[node]);
}

void unite(int u, int v){
    u = f(u), v = f(v);
    if(u == v) return;
    if(-dsu[u] < -dsu[v]) swap(u, v);
    dsu[u] += dsu[v];
    dsu[v] = u;  
}

vector<array<int, 2>> Q; 
vector<bool> ans;

int main(){
    memset(dsu, -1, sizeof(dsu));
    cin >> n >> m; 
    for(int i = 1; i <= n + m - 1; i++){
        string s; cin >> s;
        if(s[0] == 'S'){
            int u, v; cin >> u >> v;
            g[u].push_back({v, i});
            g[v].push_back({u, i});
            Q.push_back({-u, -v});
        }
        else{
            int u, a; cin >> u >> a;
            Q.push_back({a, u});
        }
    }
    dp[1][0] = 1;
    dp[1][1] = 1;
    dfs(1, 1);
    for(int j = 1; j < LOGMAX; j++){
        for(int i = 1; i <= n; i++){
            par[j][i] = par[j - 1][par[j - 1][i]];
        }
    }
    for(auto a : Q){
        if(a[0] < 0){
            unite(-a[0], -a[1]);
            continue;
        }
        if(a[0] == a[1]){
            cout << "yes\n";
            continue;
        }
        if(f(a[0]) != f(a[1])){
            cout << "no\n";
            continue;
        }
        if(!isAnc(a[0], a[1]) && !isAnc(a[1], a[0]) && parl[lift(a[0], a[1])] > parl[lift(a[1], a[0])]){
            cout << "no\n";
            continue;
        }
        int l = lca(a[0], a[1]);
        if(h[dp[a[1]][1]] <= h[l] && h[dp[a[0]][0]] <= h[l]) cout << "yes\n";
        else cout << "no\n";
    }
}

• 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