Submission #736432

#	Time	Username	Problem	Language	Result	Execution time	Memory
736432		He_Huanglu	Inside information (BOI21_servers)	C++17	100 / 100	624 ms	35844 KiB

servers

#include <bits/stdc++.h>
#define ii pair<int, int>
using namespace std;

const int N = 12e4 + 5, S = 17;
int n, nq, f[N], anc[N], sz[N], ans[2 * N], dis[N], par[N][S], tang[N], giam[N], bit[2 * N];
bool block[N], inc[N], red[N];
vector <ii> ke[N], cur;
vector <int> ques[N];
struct sieungu {
    int fi, se, th;
}; vector <sieungu> dull;

void dfs(int u, int pre, int p) {
    for(auto [v, w] : ke[u]) if(!block[v] && v != pre) {
        f[v] = w;
        if(!p) {
            anc[v] = v;
            inc[v] = red[v] = 1;
            cur.push_back({v, w});
        }
        else {
            inc[v] = (inc[u] && f[v] > f[u]);
            red[v] = (red[u] && f[v] < f[u]);
            anc[v] = anc[u];
        }
        if(red[v]) {
            for(int i : ques[v]) if(f[anc[v]] < i) ans[i]++;
        }
        dfs(v, u, anc[v]);
    }
}

void upd(int u, int pre, int val) {
    if(inc[u]) {
        int x = f[u];
        while (x < n + nq) {
            bit[x] += val;
            x += (x & -x);
        }
    }
    for(auto [v, w] : ke[u]) if(!block[v] && v != pre) upd(v, u, val);
}
int get(int x) {
    int ret = 0;
    while (x) {
        ret += bit[x];
        x -= (x & -x);
    }
    return ret;
}

void scan(int u, int pre) {
    if(red[u]) {
        for(auto i : ques[u]) if(f[anc[u]] < i) ans[i] += get(i) - get(f[anc[u]]);
    }
    for(auto [v, w] : ke[u]) if(v != pre && !block[v]) scan(v, u);
}

void solve(int u) {
    f[u] = 0, inc[u] = 1, red[u] = 1, anc[u] = 0;
    cur.clear();
    dfs(u, 0, 0);
    sort(cur.begin(), cur.end(), [] (ii x, ii y) {
        return x.second > y.second;
    });
    for(auto [v, w] : cur) {
        scan(v, u);
        upd(v, 0, 1);
    }
    for(int i : ques[u]) ans[i] += get(i);
    for(auto [v, w] : cur) upd(v, 0, -1);
}

int cnt(int u, int pre) {
    sz[u] = 1;
    for(auto [v, w] : ke[u]) if(v != pre && !block[v]) sz[u] += cnt(v, u);
    return sz[u];
}

int centroid(int u, int pre, int cnt) {
    for(auto [v, w] : ke[u]) if(!block[v] && v != pre && sz[v] > cnt / 2) return centroid(v, u, cnt);
    return u;
}

void build(int u) {
    int cen = centroid(u, 0, cnt(u, 0));
    block[cen] = 1;
    solve(cen);
    for(auto [v, w] : ke[cen]) if(!block[v]) build(v);
}

void dfss(int u, int pre) {
    for(auto [v, w] : ke[u]) if(v != pre) {
        dis[v] = dis[u] + 1;
        f[v] = w;
        if(!pre) tang[v] = giam[v] = 1;
        else {
            tang[v] = (f[v] > f[u] ? tang[u] + 1 : 1);
            giam[v] = (f[v] < f[u] ? giam[u] + 1 : 1);
        }
        par[v][0] = u;
        for(int i = 1; i < S; i++) par[v][i] = par[par[v][i - 1]][i - 1];
        dfss(v, u);
    }
}

int lca(int u, int v) {
    if(dis[u] < dis[v]) swap(u, v);
    int delta = dis[u] - dis[v];
    for(int i = S - 1; i >= 0; i--) if((delta >> i) & 1) u = par[u][i];
    if(u == v) return u;
    for(int i = S - 1; i >= 0; i--) if(par[u][i] != par[v][i])
        u = par[u][i], v = par[v][i];
    return par[v][0];
}

int pre_lca(int u, int o) {
    int delta = dis[u] - dis[o] - 1;
    for(int i = S - 1; i >= 0; i--) if((delta >> i) & 1) u = par[u][i];
    return u;
}

main () {
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("task.inp", "r")) {
        freopen("task.inp", "r", stdin);
        freopen("wa.out", "w", stdout);
    }
    cin >> n >> nq; nq += n - 1;
    for(int i = 1; i <= nq; i++) {
        char type; cin >> type;
        if(type == 'S') {
            int a, b; cin >> a >> b;
            ke[a].push_back({b, i});
            ke[b].push_back({a, i});
            ans[i] = -1;
        }
        if(type == 'Q') {
            int a, d; cin >> a >> d;
            dull.push_back({a, d, i});
            ans[i] = -2;
        }
        if(type == 'C') {
            int d; cin >> d;
            ques[d].push_back(i);
        }
    }
    dfss(1, 0);
    for(auto [a, d, i] : dull) {
        int o = lca(a, d), x = pre_lca(d, o);
        int s1 = dis[d] - dis[o], s2 = dis[a] - dis[o];
        if((s1 == giam[d] - giam[o] || giam[d] == s1) && (s2 == tang[a] - tang[o] || tang[a] == s2)) {
            if((f[pre_lca(d, o)] < f[pre_lca(a, o)] && f[a] < i) || (a == o && f[x] < i) || (d == o && f[a] < i))
                ans[i] = -3;
        }
    }
    build(1);
    for(int i = 1; i <= nq; i++) {
        if(ans[i] >= 0) cout << ans[i] + 1 << "\n";
        else if(ans[i] == -3) cout << "yes\n";
        else if(ans[i] == -2) cout << "no\n";
    }
}

Compilation message (stderr)

servers.cpp:124:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  124 | main () {
      | ^~~~
servers.cpp: In function 'int main()':
servers.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen("wa.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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