Submission #446875

#	Time	Username	Problem	Language	Result	Execution time	Memory
446875		wiwiho	Inside information (BOI21_servers)	C++14	50 / 100	385 ms	31528 KiB

servers

#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define F first
#define S second

using namespace std;

typedef long long ll;

using pii = pair<int, int>;

int n, k;
const int SZ = 20;

vector<vector<pii>> g;
vector<int> pw;
vector<vector<int>> anc;
vector<vector<bool>> incr, decr;
vector<int> in, out, dpt;
int ts = 0;

void dfs(int now, int p, int w, int d){
    in[now] = ts++;
    anc[0][now] = p;
    pw[now] = w;
    dpt[now] = d;
    if(pw[now] > pw[p]) incr[0][now] = true;
    else decr[0][now] = true;
    for(pii i : g[now]){
        if(i.F == p) continue;
        dfs(i.F, now, i.S, d + 1);
    }
    out[now] = ts++;
}

void buildAnc(){
    for(int i = 1; i < SZ; i++){
        for(int j = 1; j <= n; j++){
            anc[i][j] = anc[i - 1][anc[i - 1][j]];
            incr[i][j] = incr[i - 1][j] || incr[i - 1][anc[i - 1][j]];
            decr[i][j] = decr[i - 1][j] || decr[i - 1][anc[i - 1][j]];
        }
    }
}

bool isAnc(int a, int b){
    return in[a] <= in[b] && out[a] >= out[b];
}

int lca(int a, int b){
    if(isAnc(a, b)) return a;
    for(int i = SZ - 1; i >= 0; i--){
        if(!isAnc(anc[i][a], b)) a = anc[i][a];
    }
    return anc[0][a];
}

int jump(int a, int len){
    for(int i = 0; i < SZ; i++){
        if(1 << i & len) a = anc[i][a];
    }
    return a;
}

bool checkInc(int a, int len){
    for(int i = 0; i < SZ; i++){
        if(!(1 << i & len)) continue;
        if(incr[i][a]) return false;
        a = anc[i][a];
    }
    return true;
}

bool checkDec(int a, int len){
    for(int i = 0; i < SZ; i++){
        if(!(1 << i & len)) continue;
        if(decr[i][a]) return false;
        a = anc[i][a];
    }
    return true;
}

bool check(int u, int v, int tm){ // u to v increasing
    if(u == v) return true;
    int l = lca(u, v);
    int du = dpt[u] - dpt[l];
    int dv = dpt[v] - dpt[l];
    if(du >= 2){
        if(!checkInc(u, du - 1)) return false;
    }
    if(dv >= 2){
        if(!checkDec(v, dv - 1)) return false;
    }
    if(du > 0 && dv > 0){
        int tu = jump(u, du - 1);
        int tv = jump(v, dv - 1);
        if(pw[tu] > pw[tv]) return false;
    }
    if(dv > 0){
        if(pw[v] > tm) return false;
    }
    else{
        if(pw[jump(u, du - 1)] > tm) return false;
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;

    g.resize(n + 1);
    anc.resize(SZ, vector<int>(n + 1));
    incr.resize(SZ, vector<bool>(n + 1));
    decr.resize(SZ, vector<bool>(n + 1));
    pw.resize(n + 1);
    in.resize(n + 1);
    out.resize(n + 1);
    dpt.resize(n + 1);

    vector<pair<int, pii>> qry;
    for(int i = 0; i < n + k - 1; i++){
        string s;
        cin >> s;
        assert(s != "C");
        if(s == "S"){
            int u, v;
            cin >> u >> v;
            g[u].eb(mp(v, i));
            g[v].eb(mp(u, i));
            continue;
        }
        int v, d;
        cin >> v >> d;
        qry.eb(mp(i, mp(v, d)));
    }

    dfs(1, 1, 0, 0);
    buildAnc();

    for(auto i : qry){
        int tm = i.F;
        int v = i.S.F;
        int d = i.S.S;
        if(check(d, v, tm)) cout << "yes\n";
        else cout << "no\n";
    }

    return 0;
}

• 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