Submission #895294

#	Time	Username	Problem	Language	Result	Execution time	Memory
895294		TahirAliyev	Inside information (BOI21_servers)	C++17	0 / 100	81 ms	15452 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)];
}


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

int main(){
    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});
        }
        else{
            int u, a; cin >> u >> a;
            Q.push_back({a, u, i});
        }
    }
    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] == a[1]){
            ans.push_back(1);
            continue;
        }
        if(parl[lift(a[0], a[1])] > parl[lift(a[1], a[0])] || parl[a[1]] > a[2]){
            ans.push_back(0);
            continue;
        }
        int l = lca(a[0], a[1]);
        if(h[dp[a[0]][1]] >= h[l] && h[dp[a[1]][0]] >= h[l]) ans.push_back(1);
        else ans.push_back(0);
    }
    for(bool i : ans) cout << (i? "yes" : "no") << '\n';
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5