oj.uz

Submission #733143

# Submission time Handle Problem Language Result Execution time Memory
733143 2023-04-30T07:13:40 Z nguyentunglam Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 34744 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 2e5 + 10;
bool dd[N];
int sz[N], ans[N];
vector<pair<int, int>> adj[N], query1[N];
vector<int> query2[N];
int n, k, cnt[N], type[N];


int calc(int u, int par) {
    sz[u] = 1;
    for(auto &[v, w] : adj[u]) if (!dd[v] && v != par) {
        sz[u] += calc(v, u);
    }
    return sz[u];
}

int getcentr(int u, int par, int cnt) {
    for(auto &[v, w] : adj[u]) if (!dd[v] && v != par && sz[v] > 2 * cnt)
        return getcentr(v, u, cnt);
    return u;
}
int bit[N << 1];

void up(int pos, int val) {
    while (pos <= k) {
        bit[pos] += val;
        pos += pos & -pos;
    }
}

int get(int pos) {
    int ret = 0;
    while (pos) {
        ret += bit[pos];
        pos -= pos & -pos;
    }
    return ret;
}

void dfs1(int u, int pre) {
    up(pre, 1);
    cnt[u] = pre;
    for(auto &[v, w] : adj[u]) if (!dd[v] && w > pre) {
        dfs1(v, w);
    }
}

void dfs2(int u, int pre) {
    for(int &idx : query2[u]) {
        ans[idx] += get(idx);
    }
    for(auto &[a, idx] : query1[u]) {
        ans[idx] |= (cnt[a] > 0 && cnt[a] < idx);
    }

    for(auto &[v, w] : adj[u]) if (!dd[v] && w < pre) {
        dfs2(v, w);
    }
}

void dfs3(int u, int pre) {
    up(pre, -1);
    cnt[u] = 0;
    for(auto &[v, w] : adj[u]) if (!dd[v] && w > pre) {
        dfs3(v, w);
    }
}

void centroid(int u) {
    int node = getcentr(u, u, calc(u, u));
    dd[node] = 1;
//    cout << node << endl;
    vector<pair<int, int> > lst;
    for(auto &[v, w] : adj[node]) if (!dd[v]) lst.emplace_back(-w, v);
    sort(lst.begin(), lst.end());
    for(auto &[w, v] : lst) {
        w = -w;
        cnt[node] = w;
        up(w, 1);
        dfs2(v, w);
        up(w, -1);
        cnt[node] = 0;
        dfs1(v, w);
    }
    for(int &idx : query2[node]) {
        ans[idx] += get(idx);
    }
    for(auto &[a, idx] : query1[node]) {
        ans[idx] |= (cnt[a] > 0 && cnt[a] < idx);
    }
    for(auto &[w, v] : lst) {
        dfs3(v, w);
    }
    for(auto &[v, w] : adj[node]) if (!dd[v]) centroid(v);
}

int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    cin >> n >> k;
    k = n + k - 1;
    for(int i = 1; i <= k; i++) {
        char c; cin >> c;
        if (c == 'S') {
            int a, b; cin >> a >> b;
            adj[a].emplace_back(b, i);
            adj[b].emplace_back(a, i);
        }
        if (c == 'Q') {
            int a, d; cin >> a >> d;
            if (a == d) ans[i] = 1;
            query1[d].emplace_back(a, i);
            type[i] = 1;
        }
        if (c == 'C') {
            int d; cin >> d;
            query2[d].push_back(i);
            type[i] = 2;
            ans[i] = 1;
        }
    }
    centroid(1);
    for(int i = 1; i <= k; i++) {
        if (type[i] == 1) cout << (ans[i] ? "yes\n" : "no\n");
        else if (type[i] == 2) cout << ans[i] << endl;
    }

}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:107:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:108:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:111:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:112:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17924 KB Output is correct
2 Correct 38 ms 19404 KB Output is correct
3 Correct 38 ms 19204 KB Output is correct
4 Correct 77 ms 19496 KB Output is correct
5 Correct 176 ms 19388 KB Output is correct
6 Correct 36 ms 19196 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17924 KB Output is correct
2 Correct 38 ms 19404 KB Output is correct
3 Correct 38 ms 19204 KB Output is correct
4 Correct 77 ms 19496 KB Output is correct
5 Correct 176 ms 19388 KB Output is correct
6 Correct 36 ms 19196 KB Output is correct
7 Correct 29 ms 18452 KB Output is correct
8 Correct 48 ms 18716 KB Output is correct
9 Correct 43 ms 18580 KB Output is correct
10 Correct 76 ms 18848 KB Output is correct
11 Correct 184 ms 18848 KB Output is correct
12 Correct 45 ms 18508 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17964 KB Output is correct
2 Incorrect 159 ms 28816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17964 KB Output is correct
2 Incorrect 159 ms 28816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 17956 KB Output is correct
2 Execution timed out 3533 ms 34744 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 17956 KB Output is correct
2 Execution timed out 3533 ms 34744 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17920 KB Output is correct
2 Incorrect 213 ms 28428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17920 KB Output is correct
2 Incorrect 213 ms 28428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 17904 KB Output is correct
2 Execution timed out 3509 ms 34628 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 17904 KB Output is correct
2 Execution timed out 3509 ms 34628 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17984 KB Output is correct
2 Correct 41 ms 19408 KB Output is correct
3 Correct 39 ms 19264 KB Output is correct
4 Correct 83 ms 19560 KB Output is correct
5 Correct 195 ms 19480 KB Output is correct
6 Correct 36 ms 19148 KB Output is correct
7 Correct 27 ms 18636 KB Output is correct
8 Incorrect 151 ms 28724 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17984 KB Output is correct
2 Correct 41 ms 19408 KB Output is correct
3 Correct 39 ms 19264 KB Output is correct
4 Correct 83 ms 19560 KB Output is correct
5 Correct 195 ms 19480 KB Output is correct
6 Correct 36 ms 19148 KB Output is correct
7 Correct 27 ms 18636 KB Output is correct
8 Incorrect 151 ms 28724 KB Output isn't correct
9 Halted 0 ms 0 KB -