oj.uz

Submission #733149

# Submission time Handle Problem Language Result Execution time Memory
733149 2023-04-30T07:21:58 Z nguyentunglam Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 28236 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 = 120000 + 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;
    if (n <= 1e5) {
        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: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.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:109:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
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".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:113:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12108 KB Output is correct
2 Correct 41 ms 13804 KB Output is correct
3 Correct 34 ms 13516 KB Output is correct
4 Correct 78 ms 13940 KB Output is correct
5 Correct 173 ms 13772 KB Output is correct
6 Correct 43 ms 13532 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12108 KB Output is correct
2 Correct 41 ms 13804 KB Output is correct
3 Correct 34 ms 13516 KB Output is correct
4 Correct 78 ms 13940 KB Output is correct
5 Correct 173 ms 13772 KB Output is correct
6 Correct 43 ms 13532 KB Output is correct
7 Correct 28 ms 12804 KB Output is correct
8 Correct 43 ms 13128 KB Output is correct
9 Correct 34 ms 12896 KB Output is correct
10 Correct 82 ms 13204 KB Output is correct
11 Correct 185 ms 13132 KB Output is correct
12 Correct 34 ms 12928 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12116 KB Output is correct
2 Incorrect 97 ms 20392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12116 KB Output is correct
2 Incorrect 97 ms 20392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12060 KB Output is correct
2 Execution timed out 3555 ms 28120 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 12060 KB Output is correct
2 Execution timed out 3555 ms 28120 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12112 KB Output is correct
2 Incorrect 103 ms 21476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12112 KB Output is correct
2 Incorrect 103 ms 21476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12108 KB Output is correct
2 Execution timed out 3550 ms 28236 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12108 KB Output is correct
2 Execution timed out 3550 ms 28236 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12092 KB Output is correct
2 Correct 49 ms 13728 KB Output is correct
3 Correct 58 ms 13508 KB Output is correct
4 Correct 77 ms 13900 KB Output is correct
5 Correct 183 ms 13852 KB Output is correct
6 Correct 40 ms 13576 KB Output is correct
7 Correct 33 ms 13004 KB Output is correct
8 Incorrect 100 ms 20404 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12092 KB Output is correct
2 Correct 49 ms 13728 KB Output is correct
3 Correct 58 ms 13508 KB Output is correct
4 Correct 77 ms 13900 KB Output is correct
5 Correct 183 ms 13852 KB Output is correct
6 Correct 40 ms 13576 KB Output is correct
7 Correct 33 ms 13004 KB Output is correct
8 Incorrect 100 ms 20404 KB Output isn't correct
9 Halted 0 ms 0 KB -