oj.uz

Submission #1004630

# Submission time Handle Problem Language Result Execution time Memory
1004630 2024-06-21T10:56:25 Z LOLOLO Synchronization (JOI13_synchronization) C++14
100 / 100
 191 ms 25800 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 1e5 + 10;
vector <int> ed[N];
int p[N][20], f[N], in[N], ou[N], timer = 1, num[N], pr[N], used[N];
 
void upd(int i, int x) {
    for (; i < N; i += i & (-i))
        f[i] += x;
}
 
int get(int i) {
    int s = 0;
    for (; i; i -= i & (-i))
        s += f[i];
 
    return s;
} 
 
void dfs(int u, int v) {
    in[u] = timer++;
    p[u][0] = v;
    for (int j = 1; j < 20; j++)
        p[u][j] = p[p[u][j - 1]][j - 1];
 
    for (auto x : ed[u]) {
        if (x == v)
            continue;
 
        dfs(x, u);
    }
 
    ou[u] = timer;
    upd(in[u], 1);
    upd(ou[u], -1);
}
 
int root(int x) {
    int v = get(in[x]);
 
    for (int j = 19; j >= 0; j--) {
        if (get(in[p[x][j]]) == v)
            x = p[x][j];
    }
 
    return x;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n, m, q;
    cin >> n >> m >> q;
 
    vector <pair <int, int>> save;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        ed[a].pb(b);
        ed[b].pb(a);
        save.pb({a, b});
    }
 
    dfs(1, 1);
 
    for (int i = 1; i <= n; i++) {
        num[i] = 1;
    }
 
    for (int i = 1; i <= m; i++) {
        int id;
        cin >> id;
        id--;
        int a = save[id].f, b = save[id].s;
        if (p[a][0] == b)
            swap(a, b);
 
        if (used[id] == -1) {
            // remove edge
            int r = root(a);
            upd(in[b], 1);
            upd(ou[b], -1);
            num[b] = used[id] = num[r];
        } else {
            // insert edge
            int r = root(a);
            upd(in[b], -1);
            upd(ou[b], 1);
            num[r] += num[b] - used[id];
            used[id] = -1;
        } 
    }
 
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        cout << num[root(x)] << '\n';
    }
 
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2820 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 12 ms 4444 KB Output is correct
8 Correct 15 ms 4444 KB Output is correct
9 Correct 11 ms 4444 KB Output is correct
10 Correct 166 ms 18784 KB Output is correct
11 Correct 147 ms 18888 KB Output is correct
12 Correct 184 ms 25024 KB Output is correct
13 Correct 76 ms 18620 KB Output is correct
14 Correct 120 ms 18116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 21800 KB Output is correct
2 Correct 71 ms 21444 KB Output is correct
3 Correct 67 ms 24260 KB Output is correct
4 Correct 70 ms 24436 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2904 KB Output is correct
7 Correct 15 ms 5128 KB Output is correct
8 Correct 184 ms 25800 KB Output is correct
9 Correct 191 ms 25800 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 25796 KB Output is correct
2 Correct 95 ms 25284 KB Output is correct
3 Correct 104 ms 25520 KB Output is correct
4 Correct 105 ms 25536 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 12 ms 4444 KB Output is correct
7 Correct 147 ms 19656 KB Output is correct
8 Correct 184 ms 25800 KB Output is correct
9 Correct 88 ms 19892 KB Output is correct
10 Correct 115 ms 19396 KB Output is correct
11 Correct 86 ms 22980 KB Output is correct
12 Correct 89 ms 22980 KB Output is correct
13 Correct 91 ms 25528 KB Output is correct