제출 #646750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646750		dooompy	Inside information (BOI21_servers)	C++17	100 / 100	831 ms	62440 KiB

servers

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

struct edge {
    int to, cost;

    bool operator <(edge o) const {
        return cost > o.cost;
    }
};

const int MAXN = 3e5;

int tree[4 * MAXN];

void update(int x, int l, int r, int p, int v) {
    if (l == r) {
        tree[x] += v;
        return;
    }

    int mid = (l + r) / 2;
    if (p <= mid) update(2 * x, l, mid, p, v);
    else update(2 * x + 1, mid + 1, r, p, v);

    tree[x] = tree[2 * x] + tree[2 * x + 1];
}

int query(int x, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[x];
    if (l > qr || ql > r) return 0;

    int mid = (l + r) / 2;

    return query(2 * x, l, mid, ql, qr) + query(2 * x + 1, mid + 1, r, ql, qr);
}

set<edge> adj[200005];
set<pair<int, int>> query_q[200005];
vector<int> query_c[200005];
int ans[300005];
int sz[200005];

void dfs_centroid(int node, int par = -1) {
    sz[node] = 1;

    for (auto nxt : adj[node]) {
        if (nxt.to == par) continue;
        dfs_centroid(nxt.to, node);
        sz[node] += sz[nxt.to];
    }

    return;
}

int find_centroid(int node, int total, int par = -1) {
    for (auto nxt : adj[node]) {
        if (nxt.to == par) continue;
        if (sz[nxt.to] > total / 2) return find_centroid(nxt.to, total, node);
    }

    return node;
}

vector<int> children;
map<int, int> L;

void dfs_one(int node, int par, int cost) {
    auto itr = query_q[node].begin();

    while (itr != query_q[node].end()) {
        auto m_itr = L.find(itr->first);

        if (m_itr == L.end() || m_itr->second > itr->second) {
            itr++; continue;
        }

        ans[itr->second] = -1;
        itr = query_q[node].erase(itr);
    }

    children.push_back(node);

    for (auto nxt : adj[node]) {
        if (nxt.to == par) continue;
        if (nxt.cost < cost) dfs_one(nxt.to, node, nxt.cost);
    }
}

vector<pair<int, int>> rev;

void dfs_two(int node, int par, int cost) {
    L[node] = cost;
    update(1, 1, MAXN, cost, 1);
    rev.push_back({cost, -1});

    for (auto nxt : adj[node]) {
        if (nxt.to == par) continue;
        if (nxt.cost > cost) dfs_two(nxt.to, node, nxt.cost);
    }
}

void solve(int node) {
    L.clear();

    for (auto nxt : adj[node]) {
        children.clear();
        L[node] = nxt.cost;
        dfs_one(nxt.to, node, nxt.cost);

        for (auto child : children) {
            for (auto q : query_c[child]) {
                if (q > nxt.cost) {
                    ans[q] += query(1, 1, MAXN, 1, q) + 1;
                }
            }
        }

        dfs_two(nxt.to, node, nxt.cost);
    }

    auto itr = query_q[node].begin();

    while (itr != query_q[node].end()) {
        auto m_itr = L.find(itr->first);

        if (m_itr == L.end() || m_itr->second > itr->second) {
            itr++; continue;
        }

        ans[itr->second] = -1;
        itr = query_q[node].erase(itr);
    }

    for (auto q : query_c[node]) {
            ans[q] += query(1, 1, MAXN, 1, q) + 1;
    }

    while (!rev.empty()) {
        update(1, 1, MAXN, rev.back().first, rev.back().second);
        rev.pop_back();
    }
}

void centroid(int node) {
    dfs_centroid(node);

    int cent = find_centroid(node, sz[node]);

    solve(cent);

    // clean up

    vector<edge> del(adj[cent].begin(), adj[cent].end());

    for (auto e : del) {
        adj[cent].erase(e);
        adj[e.to].erase(adj[e.to].find({cent, e.cost}));
        centroid(e.to);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, k; cin >> n >> k;

    fill(ans, ans+300005, -3);

    for (int i = 1; i <= n + k -1; i++) {
        char type; cin >> type;
        if (type == 'S') {
            int a, b; cin >> a >> b;
            adj[a].insert({b, i});
            adj[b].insert({a, i});
        } else if (type == 'Q') {
            int a, b; cin >> a >> b;
            // if b can reach a
            if (a == b) ans[i] = -1;
            else {
                query_q[b].insert({a, i});
                ans[i] = -2;
            }
        } else {
            // type c
            int d; cin >> d;
            query_c[d].push_back(i);
            ans[i] = 0;
        }
    }

    centroid(1);

    for (int i = 1; i <= n + k - 1; i++) {
        if (ans[i] == -3) continue;
        if (ans[i] >= 0) {
            cout << ans[i];
        } else {
            cout << (ans[i] == -1 ? "yes" : "no");
        }

        cout << "\n";
    }
}

• 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