oj.uz

Submission #733145

# Submission time Handle Problem Language Result Execution time Memory
733145 2023-04-30T07:17:54 Z nguyentunglam Inside information (BOI21_servers) C++17
30 / 100
 3500 ms 34364 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 = 240000 + 10;
bool dd[N];
int sz[N], ans[N << 1];
vector<pair<int, int>> adj[N], query1[N];
vector<int> query2[N];
int n, k, cnt[N], type[N << 1];


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;
    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:106:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:110:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20496 KB Output is correct
2 Correct 38 ms 20804 KB Output is correct
3 Correct 35 ms 20720 KB Output is correct
4 Correct 82 ms 21028 KB Output is correct
5 Correct 167 ms 20868 KB Output is correct
6 Correct 38 ms 20684 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20496 KB Output is correct
2 Correct 38 ms 20804 KB Output is correct
3 Correct 35 ms 20720 KB Output is correct
4 Correct 82 ms 21028 KB Output is correct
5 Correct 167 ms 20868 KB Output is correct
6 Correct 38 ms 20684 KB Output is correct
7 Correct 37 ms 20400 KB Output is correct
8 Correct 49 ms 20380 KB Output is correct
9 Correct 36 ms 20304 KB Output is correct
10 Correct 72 ms 20556 KB Output is correct
11 Correct 191 ms 20384 KB Output is correct
12 Correct 37 ms 20172 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20608 KB Output is correct
2 Correct 155 ms 29148 KB Output is correct
3 Correct 158 ms 29140 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20608 KB Output is correct
2 Correct 155 ms 29148 KB Output is correct
3 Correct 158 ms 29140 KB Output is correct
4 Correct 30 ms 20436 KB Output is correct
5 Correct 153 ms 28852 KB Output is correct
6 Correct 124 ms 27296 KB Output is correct
7 Correct 100 ms 27324 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 20468 KB Output is correct
2 Execution timed out 3559 ms 34228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 20468 KB Output is correct
2 Execution timed out 3559 ms 34228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 20564 KB Output is correct
2 Correct 214 ms 28392 KB Output is correct
3 Correct 229 ms 28236 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 20564 KB Output is correct
2 Correct 214 ms 28392 KB Output is correct
3 Correct 229 ms 28236 KB Output is correct
4 Correct 29 ms 20448 KB Output is correct
5 Correct 231 ms 28904 KB Output is correct
6 Correct 196 ms 28492 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20556 KB Output is correct
2 Execution timed out 3544 ms 34364 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20556 KB Output is correct
2 Execution timed out 3544 ms 34364 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 20572 KB Output is correct
2 Correct 45 ms 20824 KB Output is correct
3 Correct 37 ms 20692 KB Output is correct
4 Correct 72 ms 21012 KB Output is correct
5 Correct 169 ms 20912 KB Output is correct
6 Correct 36 ms 20700 KB Output is correct
7 Correct 28 ms 20564 KB Output is correct
8 Correct 154 ms 29040 KB Output is correct
9 Correct 150 ms 29028 KB Output is correct
10 Correct 28 ms 20556 KB Output is correct
11 Execution timed out 3573 ms 34096 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 20572 KB Output is correct
2 Correct 45 ms 20824 KB Output is correct
3 Correct 37 ms 20692 KB Output is correct
4 Correct 72 ms 21012 KB Output is correct
5 Correct 169 ms 20912 KB Output is correct
6 Correct 36 ms 20700 KB Output is correct
7 Correct 28 ms 20564 KB Output is correct
8 Correct 154 ms 29040 KB Output is correct
9 Correct 150 ms 29028 KB Output is correct
10 Correct 28 ms 20556 KB Output is correct
11 Execution timed out 3573 ms 34096 KB Time limit exceeded
12 Halted 0 ms 0 KB -