Submission #1306807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306807		Wansur	Inside information (BOI21_servers)	C++20	60 / 100	277 ms	61580 KiB

servers

#include <bits/stdc++.h>
#define ent '\n'
#define int long long

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

typedef long long ll;
using namespace std;

const int maxn = 1'000'000 + 12;
const int mod = 998'244'353;

vector<pair<int, int>> g[maxn];
vector<int> que[maxn];
int d[maxn], a[maxn], fr[maxn], pr[maxn];
int up[22][maxn], tin[maxn], tout[maxn];
int p[maxn], sz[maxn], mxs[maxn], ans[maxn];
int n, m, timer;

bool del[maxn];

int f[maxn];
vector<pair<int, int>> cl;

void upd(int i, int x) {
    cl.push_back({i, x});
    for(; i < maxn; i |= (i + 1)) {
        f[i] += x;
    }
}

int get_f(int i) {
    int ans = 0;
    for(; i >= 0; i = (i & (i + 1)) - 1) {
        ans += f[i];
    }
    return ans;
}

void init() {
    for(auto [i, x] : cl) {
        upd(i, -x);
    }
    cl.clear();
}

void pre_calc(int v, int p) {
    sz[v] = 1;
    mxs[v] = 0;

    for(auto [to, i] : g[v]) {
        if(del[to] || to == p) {
            continue;
        }

        pre_calc(to, v);
        sz[v] += sz[to];

        if(sz[mxs[v]] < sz[to]) {
            mxs[v] = to;
        }
    }
}

void dfs_get(int v, int p) {
    if(a[v] > a[p]) {
        return;
    }

    for(int i : que[v]) {
        ans[i] += get_f(i);
    }

    for(auto [to, w] : g[v]) {
        if(del[to] || to == p) {
            continue;
        }

        a[to] = w;
        dfs_get(to, v);
    }
}

void dfs_upd(int v, int p) {
    if(a[v] < a[p]) {
        return;
    }

    upd(a[v], 1);
    for(auto [to, w] : g[v]) {
        if(to == p || del[to]) {
            continue;
        }

        a[to] = w;
        dfs_upd(to, v);
    }
}

void centroid(int v) {
    pre_calc(v, 0);

    int total = sz[v];
    while(sz[mxs[v]] * 2 > total) {
        v = mxs[v];
    }

    del[v] = true;
    a[v] = 0;

    vector<pair<int, int>> adj;

    for(auto [to, x] : g[v]) {
        if(del[to]) {
            continue;
        }
        adj.push_back({x, to});
    }

    sort(adj.begin(), adj.end());
    reverse(adj.begin(), adj.end());

    init();

    for(auto [x, to] : adj) {
        a[v] = maxn - 1;

        a[to] = x;
        upd(x, 1);
        dfs_get(to, v);
        upd(x, -1);

        a[v] = 0;

        dfs_upd(to, v);
    }

    for(int i : que[v]) {
        ans[i] += get_f(i);
    }


    for(auto [x, to] : adj) {
        if(!del[to]) centroid(to);
    }
}

int get(int x) {
    if(p[x] == x) return x;
    return p[x] = get(p[x]);
}

void pre_dfs(int v, int p) {
    d[v] = d[p] + 1;
    if(p <= 1) {
        fr[v] = 1;
    }
    else {
        if(pr[p] == 1 || (a[v] < a[p]) == (a[p] < a[pr[p]])) {
            fr[v] = fr[p];
        }
        else fr[v] = pr[p];
    }
    up[0][v] = p;
    for(int i = 1; i < 20; i++) {
        up[i][v] = up[i - 1][up[i - 1][v]];
    }
    tin[v] = ++timer;
    pr[v] = p;

    for(auto [to, x] : g[v]) {
        if(to == p) {
            continue;
        }

        a[to] = x;
        pre_dfs(to, v);
    }

    tout[v] = timer;
}

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

int lca(int u, int v) {
    if(check(u, v)) return u;
    if(check(v, u)) return v;

    for(int i = 19; i >= 0; i--) {
        if(up[i][u] && !check(up[i][u], v)) {
            u = up[i][u];
        }
    }

    return up[0][u];
}

int pre_lca(int u, int v) {
    for(int i = 19; i >= 0; i--) {
        if(up[i][u] && !check(up[i][u], v)) {
            u = up[i][u];
        }
    }

    return u;
}

bool query(int u, int v) {
    if(get(u) != get(v)) {
        return false;
    }

    int lc = lca(u, v), dist = d[v] + d[u] - 2 * d[lc];

    swap(u, v);
    if(u == v || dist <= 1) {
        return true;
    }
    if(check(u, v) && a[v] > a[pr[v]] && check(fr[v], lc)) {
        return true;
    }
    if(check(v, u) && a[u] < a[pr[u]] && check(fr[u], lc)) {
        return true;
    }
    if(!check(v, u) && !check(u, v)) {
        int x = pre_lca(u, lc), y = pre_lca(v, lc);
        if(a[x] < a[y] && check(fr[u], lc) && check(fr[v], lc) && (pr[u] == lc || a[u] < a[pr[u]]) && (pr[v] == lc || a[v] > a[pr[v]])) {
            return true;
        }
    }
    return false;
}

void solve() {
    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        p[i] = i;
    }

    m += n - 1;
    vector<array<int, 3>> Q;

    for(int i = 1; i <= m; i++) {
        char c;
        int u, v;
        cin >> c >> u;

        if(c == 'S') {
            cin >> v;
            g[u].push_back({v, i});
            g[v].push_back({u, i});
            Q.push_back({0, u, v});
        }
        else if(c == 'Q') {
            cin >> v;
            Q.push_back({1, u, v});
        }
        else {
            que[u].push_back(i);
            Q.push_back({2, u, 0});
        }
    }

    centroid(1);
    pre_dfs(1, 0);

    int ptr = 0;
    for(auto [tp, u, v] : Q) {
        ptr++;

        if(tp == 2) {
            cout << ans[ptr] + 1 << ent;
        }
        else if(!tp) {
            p[get(u)] = get(v);
        }
        else {
            if(query(u, v)) {
                cout << "yes\n";
            }
            else cout << "no\n";
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
}

• Subtask 1-1: 2 / 2
• Subtask 1-2: 3 / 3
• Subtask 2-1: 0 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 5 / 5
• Subtask 3-2: 5 / 5
• Subtask 4-1: 10 / 10
• Subtask 4-2: 10 / 10
• Subtask 5-1: 12 / 12
• Subtask 5-2: 13 / 13
• Subtask 6-1: 0 / 17
• Subtask 6-2: 0 / 18