Submission #638070

#	Time	Username	Problem	Language	Result	Execution time	Memory
638070		LeonaRaging	Inside information (BOI21_servers)	C++14	50 / 100	3566 ms	71444 KiB

servers

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const ll mod = 1e9 + 7;
const int maxn = 3e5 + 4;
const int INF = 1e9;

struct Node {
    int fi, se;
    bool operator < (const Node &other) const {
        return se > other.se;
    }
};

struct seg_tree {
    vector<int> t;
    seg_tree() {
        t.resize(4 * maxn);
    }
    void update(int pos, int val, int v = 1, int l = 1, int r = maxn - 1) {
        if (l == r) {
            t[v] += val;
            return;
        }
        int m = (l + r) / 2;
        if (pos <= m) update(pos, val, 2 * v, l, m);
        else update(pos, val, 2 * v + 1, m + 1, r);
    }
    int get(int pos, int v = 1, int l = 1, int r = maxn - 1) {
        if (l == r) return t[v];
        int m = (l + r) / 2;
        if (pos <= m) return get(pos, 2 * v, l, m);
        else return get(pos, 2 * v, l, m) + get(pos, 2 * v + 1, m + 1, r);
    }
} IT;

int n, k, leave[maxn], join[maxn], reach[maxn], res[maxn];
set<Node> adj[maxn];
vector<int> query_c[maxn], cur;
set<pair<int,int>> query_q[maxn];
map<int,int> L;
stack<pair<int,int>> rev;

void dfs_in(int u, int p, int pre) {
    auto it = query_q[u].begin();
    while (it != query_q[u].end()) {
        auto idx = L.find(it->fi);
        if (idx == L.end() || idx->se > it->se) {
            it++;
            continue;
        }
        res[it->se] = -1;
        it = query_q[u].erase(it);
    }
    cur.push_back(u);
    for (auto it : adj[u]) {
        int v = it.fi, w = it.se;
        if (w < pre && v != p)
            dfs_in(v, u, w);
    }
}

void dfs_out(int u, int p, int pre) {
    L[u] = pre;
    IT.update(pre, 1);
    rev.push({pre, 1});
    for (auto it : adj[u]) {
        int v = it.fi, w = it.se;
        if (w > pre && v != p)
            dfs_out(v, u, w);
    }
}

void Solve(int u) {
    L.clear();
    for (auto it : adj[u]) {
        cur.clear();
        int v = it.fi, w = it.se;
        L[u] = w;
        dfs_in(v, u, w);
        for (auto i : cur) {
            for (auto it : query_c[i]) if (it > w) {
                res[it] += IT.get(it) + 1;
            }
        }
        dfs_out(v, u, w);
    }
    auto it = query_q[u].begin();
    while (it != query_q[u].end()) {
        auto idx = L.find(it->fi);
        if (idx == L.end() || idx->se > it->se) {
            it++;
            continue;
        }
        res[it->se] = -1;
        it = query_q[u].erase(it);
    }
    for (auto it : query_c[u]) {
        res[it] += IT.get(it) + 1;
    }
    while (!rev.empty()) {
        int u, i; tie(u, i) = rev.top(); rev.pop();
        IT.update(u, -i);
    }    
}

struct Centroid_Decomposition {
    int sz[maxn];
    int dfs(int u, int p) {
        sz[u] = 1;
        for (auto it : adj[u])
            if (it.fi != p)
                sz[u] += dfs(it.fi, u);
        return sz[u];
    }
    int Centroid(int u, int p, int tot) {
        for (auto it : adj[u])
            if (it.fi != p && sz[it.fi] > tot / 2)
                return Centroid(it.fi, u, tot);
        return u;
    }
    void build(int u) {
        int tot = dfs(u, 0);
        int c = Centroid(u, 0, tot);
        Solve(c);
        vector<Node> del(adj[c].begin(), adj[c].end());
        for (auto it : del) {
            adj[c].erase(it);
            adj[it.fi].erase(adj[it.fi].find({c, it.se}));
            build(it.fi);
        }
    }
} Cen;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n + k - 1; i++)
        res[i] = -3;
    for (int i = 1; i <= n + k - 1; i++) {
        char type; int u; cin >> type >> u;
        if (type == 'S') {
            int v; cin >> v;
            adj[u].insert({v, i});
            adj[v].insert({u, i});
        }
        else if (type == 'Q') {
            int v; cin >> v;
            if (u == v) res[i] = -1;
            else {
                query_q[v].insert({u, i});
                res[i] = -2;
            }
        }
        else {
            query_c[u].pb(i);
            res[i] = 0;
        }
    }
    Cen.build(1);
    for (int i = 1; i <= n + k - 1; i++)
        if (res[i] != -3) {
            if (res[i] >= 0) cout << res[i];
            else cout << (res[i] == -1 ? "yes" : "no");
            cout << '\n';
        }
}

• 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