Submission #735991

#	Time	Username	Problem	Language	Result	Execution time	Memory
735991		He_Huanglu	Inside information (BOI21_servers)	C++17	0 / 100	43 ms	17752 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[N], dis[N], par[N][S], tang[N], giam[N];
bool block[N], inc[N], red[N];
vector <ii> ke[N];
vector <int> vt[N], update[N], cur, ques[N], bit[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;
            vt[v].clear();
            update[v].clear();
            cur.push_back(v);
        }
        else {
            inc[v] = (inc[u] && f[v] > f[u]);
            red[v] = (red[u] && f[v] < f[u]);
            anc[v] = anc[u];
        }
        if(inc[v]) {
            vt[anc[v]].push_back(f[v]);
            update[anc[v]].push_back(f[v]);
            vt[0].push_back(f[v]);
            update[0].push_back(f[v]);
        }
        if(red[v]) {
            for(int i : ques[v]) {
                if(f[v] < i) ans[i]++;
                vt[0].push_back(i);
                vt[anc[v]].push_back(i);
            }
        }
        dfs(v, u, anc[v]);
    }
}

void upd(int i, int x) {
    x = lower_bound(vt[i].begin(), vt[i].end(), x) - vt[i].begin() + 1;
    while (x < bit[i].size()) {
        bit[i][x]++;
        x += (x & -x);
    }
}
int get(int i, int x) {
    x = lower_bound(vt[i].begin(), vt[i].end(), x) - vt[i].begin() + 1;
    int ret = 0;
    while (x) {
        ret += bit[i][x];
        x -= (x & -x);
    }
    return ret;
}

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

void solve(int u) {
    f[u] = 0, inc[u] = 1, red[u] = 1, anc[u] = 0;
    vt[0].clear(), cur.clear(), update[0].clear();
    cur.push_back(0);
    dfs(u, 0, 0);
    for(int i : ques[u]) vt[0].push_back(i);
    for(int v : cur) {
        sort(vt[v].begin(), vt[v].end());
        bit[v].clear(), bit[v].resize(vt[v].size() + 1);
        for(int i : update[v]) upd(v, i);
    }
    for(int i : ques[u]) ans[i] += get(0, i);
    scan(u, 0);
}

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

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

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);
        if(dis[d] - dis[o] == giam[d] - giam[o] &&
           dis[a] - dis[o] == tang[a] - tang[o] &&
           (f[pre_lca(d, o)] < f[pre_lca(a, o)] || a == o || d == o)  &&
           f[a] < i) ans[i] = -3;
        else ans[i] = -4;

    }
    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] == -4) cout << "no\n";
    }
}

Compilation message (stderr)

servers.cpp: In function 'void upd(int, int)':
servers.cpp:48:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     while (x < bit[i].size()) {
      |            ~~^~~~~~~~~~~~~~~
servers.cpp: At global scope:
servers.cpp:140:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  140 | main () {
      | ^~~~
servers.cpp: In function 'int main()':
servers.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• 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