oj.uz

Submission #638086

# Submission time Handle Problem Language Result Execution time Memory
638086 2022-09-04T14:55:17 Z LeonaRaging Inside information (BOI21_servers) C++14
50 / 100
 482 ms 68320 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, 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 46972 KB Output is correct
2 Correct 83 ms 47284 KB Output is correct
3 Correct 88 ms 47180 KB Output is correct
4 Correct 82 ms 47320 KB Output is correct
5 Correct 81 ms 47408 KB Output is correct
6 Correct 92 ms 47500 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 46972 KB Output is correct
2 Correct 83 ms 47284 KB Output is correct
3 Correct 88 ms 47180 KB Output is correct
4 Correct 82 ms 47320 KB Output is correct
5 Correct 81 ms 47408 KB Output is correct
6 Correct 92 ms 47500 KB Output is correct
7 Incorrect 63 ms 46744 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 46972 KB Output is correct
2 Correct 315 ms 64412 KB Output is correct
3 Correct 317 ms 64388 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 46972 KB Output is correct
2 Correct 315 ms 64412 KB Output is correct
3 Correct 317 ms 64388 KB Output is correct
4 Incorrect 69 ms 46680 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 46908 KB Output is correct
2 Correct 316 ms 61420 KB Output is correct
3 Correct 317 ms 61444 KB Output is correct
4 Correct 302 ms 68312 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 46908 KB Output is correct
2 Correct 316 ms 61420 KB Output is correct
3 Correct 317 ms 61444 KB Output is correct
4 Correct 302 ms 68312 KB Output is correct
5 Incorrect 57 ms 46664 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 46888 KB Output is correct
2 Correct 313 ms 62092 KB Output is correct
3 Correct 255 ms 57448 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 46888 KB Output is correct
2 Correct 313 ms 62092 KB Output is correct
3 Correct 255 ms 57448 KB Output is correct
4 Incorrect 59 ms 46668 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 46956 KB Output is correct
2 Correct 302 ms 61384 KB Output is correct
3 Correct 301 ms 61496 KB Output is correct
4 Correct 300 ms 68320 KB Output is correct
5 Correct 60 ms 46868 KB Output is correct
6 Correct 314 ms 62012 KB Output is correct
7 Correct 256 ms 57496 KB Output is correct
8 Correct 273 ms 58968 KB Output is correct
9 Correct 285 ms 58044 KB Output is correct
10 Correct 452 ms 60288 KB Output is correct
11 Correct 473 ms 61620 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 46956 KB Output is correct
2 Correct 302 ms 61384 KB Output is correct
3 Correct 301 ms 61496 KB Output is correct
4 Correct 300 ms 68320 KB Output is correct
5 Correct 60 ms 46868 KB Output is correct
6 Correct 314 ms 62012 KB Output is correct
7 Correct 256 ms 57496 KB Output is correct
8 Correct 273 ms 58968 KB Output is correct
9 Correct 285 ms 58044 KB Output is correct
10 Correct 452 ms 60288 KB Output is correct
11 Correct 473 ms 61620 KB Output is correct
12 Incorrect 57 ms 46668 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 46888 KB Output is correct
2 Correct 86 ms 47256 KB Output is correct
3 Correct 90 ms 47272 KB Output is correct
4 Correct 87 ms 47428 KB Output is correct
5 Correct 81 ms 47412 KB Output is correct
6 Correct 95 ms 47428 KB Output is correct
7 Correct 60 ms 46976 KB Output is correct
8 Correct 318 ms 64480 KB Output is correct
9 Correct 307 ms 64332 KB Output is correct
10 Correct 58 ms 46860 KB Output is correct
11 Correct 304 ms 61428 KB Output is correct
12 Correct 306 ms 61460 KB Output is correct
13 Correct 298 ms 68276 KB Output is correct
14 Correct 61 ms 46864 KB Output is correct
15 Correct 311 ms 62020 KB Output is correct
16 Correct 266 ms 57452 KB Output is correct
17 Correct 273 ms 59016 KB Output is correct
18 Correct 274 ms 58048 KB Output is correct
19 Correct 480 ms 60332 KB Output is correct
20 Correct 482 ms 61768 KB Output is correct
21 Correct 395 ms 63812 KB Output is correct
22 Correct 438 ms 62488 KB Output is correct
23 Correct 363 ms 59180 KB Output is correct
24 Correct 354 ms 59224 KB Output is correct
25 Correct 452 ms 61788 KB Output is correct
26 Correct 288 ms 57396 KB Output is correct
27 Correct 281 ms 57304 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 46888 KB Output is correct
2 Correct 86 ms 47256 KB Output is correct
3 Correct 90 ms 47272 KB Output is correct
4 Correct 87 ms 47428 KB Output is correct
5 Correct 81 ms 47412 KB Output is correct
6 Correct 95 ms 47428 KB Output is correct
7 Correct 60 ms 46976 KB Output is correct
8 Correct 318 ms 64480 KB Output is correct
9 Correct 307 ms 64332 KB Output is correct
10 Correct 58 ms 46860 KB Output is correct
11 Correct 304 ms 61428 KB Output is correct
12 Correct 306 ms 61460 KB Output is correct
13 Correct 298 ms 68276 KB Output is correct
14 Correct 61 ms 46864 KB Output is correct
15 Correct 311 ms 62020 KB Output is correct
16 Correct 266 ms 57452 KB Output is correct
17 Correct 273 ms 59016 KB Output is correct
18 Correct 274 ms 58048 KB Output is correct
19 Correct 480 ms 60332 KB Output is correct
20 Correct 482 ms 61768 KB Output is correct
21 Correct 395 ms 63812 KB Output is correct
22 Correct 438 ms 62488 KB Output is correct
23 Correct 363 ms 59180 KB Output is correct
24 Correct 354 ms 59224 KB Output is correct
25 Correct 452 ms 61788 KB Output is correct
26 Correct 288 ms 57396 KB Output is correct
27 Correct 281 ms 57304 KB Output is correct
28 Incorrect 59 ms 46628 KB Extra information in the output file
29 Halted 0 ms 0 KB -