oj.uz

Submission #723342

# Submission time Handle Problem Language Result Execution time Memory
723342 2023-04-13T15:49:43 Z kkts Synchronization (JOI13_synchronization) C++14
100 / 100
 308 ms 38140 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int timer, out[N], in[N], p[N][20], t[N], ans[N], last[N], f[N];
int n;
pair<int,int> e[N];
vector<int> V[N];
void dfs(int u) {
    in[u] = ++timer;
    for(int i = 1; i <= 18; i++) p[u][i] = p[p[u][i - 1]][i - 1];
    for(int i = 0; i < V[u].size(); i++) {
        if(V[u][i] != p[u][0]) p[V[u][i]][0] = u, dfs(V[u][i]);
    }
    out[u] = timer;
}
void upd(int id, int v) {
    for(id; id <= n; id += id & (-id)) t[id] += v;
}
int get(int id) {
    int ans = 0;
    for(id; id >= 1; id -= id & (-id)) ans += t[id];
    return ans;
}
int up(int u) {
    int x = get(in[u]);
    for(int i = 18; i >= 0; i--) {
        if(p[u][i] && x == get(in[p[u][i]])) u = p[u][i];
    }
    return u;
}
main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int m, q;
    cin >> n >> m >> q;
    ans[n] = 1;
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        V[u].push_back(v);
        V[v].push_back(u);
        e[i] = {u, v};
        ans[i] = 1;
    }
    dfs(1);
    for(int i = 1; i <= n; i++)
    upd(in[i], 1), upd(out[i] + 1, -1);
    while(m--) {
        int x;
        cin >> x;
        int u = e[x].f;
        if(p[e[x].s][0] == u) u = e[x].s;

        if(f[x]) {
            int root = up(u);
            f[x] = 0;
            last[x] = ans[u] = ans[root];
            upd(in[u], 1); upd(out[u] + 1, -1);
        } else {
            f[x] = 1;
            u = e[x].s + e[x].f - u;
            int root = up(u);
            ans[root] = ans[root] + ans[e[x].s + e[x].f - u] - last[x];
            upd(in[e[x].s + e[x].f - u], -1); upd(out[e[x].s + e[x].f - u] + 1, 1);
        }

    }

    while(q--) {
        int x; cin >> x;
        cout << ans[up(x)] << "\n";
    }
}

Compilation message

synchronization.cpp: In function 'void dfs(long long int)':
synchronization.cpp:15:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
synchronization.cpp: In function 'void upd(long long int, long long int)':
synchronization.cpp:21:9: warning: statement has no effect [-Wunused-value]
   21 |     for(id; id <= n; id += id & (-id)) t[id] += v;
      |         ^~
synchronization.cpp: In function 'long long int get(long long int)':
synchronization.cpp:25:9: warning: statement has no effect [-Wunused-value]
   25 |     for(id; id >= 1; id -= id & (-id)) ans += t[id];
      |         ^~
synchronization.cpp: At global scope:
synchronization.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5028 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 13 ms 7764 KB Output is correct
8 Correct 13 ms 7820 KB Output is correct
9 Correct 14 ms 7764 KB Output is correct
10 Correct 221 ms 32940 KB Output is correct
11 Correct 228 ms 32996 KB Output is correct
12 Correct 245 ms 37068 KB Output is correct
13 Correct 135 ms 32844 KB Output is correct
14 Correct 151 ms 31564 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 34172 KB Output is correct
2 Correct 85 ms 33824 KB Output is correct
3 Correct 104 ms 35788 KB Output is correct
4 Correct 104 ms 35776 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 3 ms 5088 KB Output is correct
4 Correct 3 ms 5024 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 18 ms 8284 KB Output is correct
8 Correct 308 ms 37792 KB Output is correct
9 Correct 297 ms 37836 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 37820 KB Output is correct
2 Correct 159 ms 36684 KB Output is correct
3 Correct 155 ms 36872 KB Output is correct
4 Correct 153 ms 36976 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 5 ms 5332 KB Output is correct
6 Correct 18 ms 7892 KB Output is correct
7 Correct 254 ms 33764 KB Output is correct
8 Correct 302 ms 38140 KB Output is correct
9 Correct 147 ms 33980 KB Output is correct
10 Correct 175 ms 32916 KB Output is correct
11 Correct 118 ms 35404 KB Output is correct
12 Correct 108 ms 35400 KB Output is correct
13 Correct 146 ms 36952 KB Output is correct