oj.uz

Submission #638070

# Submission time Handle Problem Language Result Execution time Memory
638070 2022-09-04T14:42:44 Z LeonaRaging Inside information (BOI21_servers) C++14
50 / 100
 3500 ms 71444 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 63 ms 46792 KB Output is correct
2 Correct 87 ms 48408 KB Output is correct
3 Correct 93 ms 48332 KB Output is correct
4 Correct 127 ms 48456 KB Output is correct
5 Correct 84 ms 48580 KB Output is correct
6 Correct 111 ms 48652 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 46792 KB Output is correct
2 Correct 87 ms 48408 KB Output is correct
3 Correct 93 ms 48332 KB Output is correct
4 Correct 127 ms 48456 KB Output is correct
5 Correct 84 ms 48580 KB Output is correct
6 Correct 111 ms 48652 KB Output is correct
7 Execution timed out 3523 ms 46860 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 46928 KB Output is correct
2 Correct 343 ms 66892 KB Output is correct
3 Correct 417 ms 66912 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 46928 KB Output is correct
2 Correct 343 ms 66892 KB Output is correct
3 Correct 417 ms 66912 KB Output is correct
4 Execution timed out 3543 ms 46848 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 46812 KB Output is correct
2 Correct 350 ms 64500 KB Output is correct
3 Correct 368 ms 64532 KB Output is correct
4 Correct 428 ms 71352 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 46812 KB Output is correct
2 Correct 350 ms 64500 KB Output is correct
3 Correct 368 ms 64532 KB Output is correct
4 Correct 428 ms 71352 KB Output is correct
5 Execution timed out 3558 ms 47044 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 46788 KB Output is correct
2 Correct 464 ms 65172 KB Output is correct
3 Correct 319 ms 60492 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 46788 KB Output is correct
2 Correct 464 ms 65172 KB Output is correct
3 Correct 319 ms 60492 KB Output is correct
4 Execution timed out 3566 ms 46920 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 69 ms 46816 KB Output is correct
2 Correct 355 ms 64612 KB Output is correct
3 Correct 352 ms 64528 KB Output is correct
4 Correct 447 ms 71444 KB Output is correct
5 Correct 60 ms 47564 KB Output is correct
6 Correct 458 ms 65116 KB Output is correct
7 Correct 316 ms 60548 KB Output is correct
8 Correct 352 ms 62080 KB Output is correct
9 Correct 331 ms 61032 KB Output is correct
10 Correct 592 ms 63312 KB Output is correct
11 Correct 603 ms 64780 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 69 ms 46816 KB Output is correct
2 Correct 355 ms 64612 KB Output is correct
3 Correct 352 ms 64528 KB Output is correct
4 Correct 447 ms 71444 KB Output is correct
5 Correct 60 ms 47564 KB Output is correct
6 Correct 458 ms 65116 KB Output is correct
7 Correct 316 ms 60548 KB Output is correct
8 Correct 352 ms 62080 KB Output is correct
9 Correct 331 ms 61032 KB Output is correct
10 Correct 592 ms 63312 KB Output is correct
11 Correct 603 ms 64780 KB Output is correct
12 Execution timed out 3541 ms 46848 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 46924 KB Output is correct
2 Correct 82 ms 48480 KB Output is correct
3 Correct 99 ms 48404 KB Output is correct
4 Correct 116 ms 48460 KB Output is correct
5 Correct 85 ms 48552 KB Output is correct
6 Correct 96 ms 48532 KB Output is correct
7 Correct 60 ms 47520 KB Output is correct
8 Correct 367 ms 66916 KB Output is correct
9 Correct 349 ms 66996 KB Output is correct
10 Correct 67 ms 47544 KB Output is correct
11 Correct 385 ms 64496 KB Output is correct
12 Correct 371 ms 64528 KB Output is correct
13 Correct 435 ms 71292 KB Output is correct
14 Correct 69 ms 47564 KB Output is correct
15 Correct 449 ms 65120 KB Output is correct
16 Correct 350 ms 60464 KB Output is correct
17 Correct 370 ms 62028 KB Output is correct
18 Correct 359 ms 61060 KB Output is correct
19 Correct 564 ms 63308 KB Output is correct
20 Correct 571 ms 64760 KB Output is correct
21 Correct 451 ms 67012 KB Output is correct
22 Correct 447 ms 65656 KB Output is correct
23 Correct 411 ms 62224 KB Output is correct
24 Correct 430 ms 62312 KB Output is correct
25 Correct 497 ms 64716 KB Output is correct
26 Correct 327 ms 60552 KB Output is correct
27 Correct 356 ms 60504 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 46924 KB Output is correct
2 Correct 82 ms 48480 KB Output is correct
3 Correct 99 ms 48404 KB Output is correct
4 Correct 116 ms 48460 KB Output is correct
5 Correct 85 ms 48552 KB Output is correct
6 Correct 96 ms 48532 KB Output is correct
7 Correct 60 ms 47520 KB Output is correct
8 Correct 367 ms 66916 KB Output is correct
9 Correct 349 ms 66996 KB Output is correct
10 Correct 67 ms 47544 KB Output is correct
11 Correct 385 ms 64496 KB Output is correct
12 Correct 371 ms 64528 KB Output is correct
13 Correct 435 ms 71292 KB Output is correct
14 Correct 69 ms 47564 KB Output is correct
15 Correct 449 ms 65120 KB Output is correct
16 Correct 350 ms 60464 KB Output is correct
17 Correct 370 ms 62028 KB Output is correct
18 Correct 359 ms 61060 KB Output is correct
19 Correct 564 ms 63308 KB Output is correct
20 Correct 571 ms 64760 KB Output is correct
21 Correct 451 ms 67012 KB Output is correct
22 Correct 447 ms 65656 KB Output is correct
23 Correct 411 ms 62224 KB Output is correct
24 Correct 430 ms 62312 KB Output is correct
25 Correct 497 ms 64716 KB Output is correct
26 Correct 327 ms 60552 KB Output is correct
27 Correct 356 ms 60504 KB Output is correct
28 Execution timed out 3558 ms 46940 KB Time limit exceeded
29 Halted 0 ms 0 KB -