oj.uz

Submission #1084137

# Submission time Handle Problem Language Result Execution time Memory
1084137 2024-09-05T10:26:18 Z Yang8on Synchronization (JOI13_synchronization) C++17
100 / 100
 196 ms 29012 KB 
#include <bits/stdc++.h>
#define Y8o "Synchronization"
#define maxn (int) 2e5 + 5
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
#define all(x) x.begin(), x.end()
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r

//#define f first
//#define s second

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

int n, m, Q, cnt;
struct dl { int u, v, id; } ed[maxn];
vector<int> o[maxn];

int h[maxn], in[maxn], out[maxn];
int cha[maxn][20];
int a[maxn], c[maxn];
void dfs(int u = 1, int p = 0) {
    in[u] = ++cnt;
    for(int v : o[u]) if(v != p) {
        h[v] = h[u] + 1;
        cha[v][0] = u;
        for(int j = 1; j <= 17; j ++) cha[v][j] = cha[cha[v][j - 1]][j - 1];
        dfs(v, u);
    }
    out[u] = cnt;
}
struct BIT {
    int bit[maxn];
    void update(int x, int val) {
        while(x <= n) { bit[x] += val, x += (x & -x); }
    }
    int get(int x, int best = 0) {
        while(x) { best += bit[x], x -= (x & -x); }
        return best;
    }
} Bit;
int par(int u) {
    for(int i = 19; i >= 0; i --) {
        if(cha[u][i] && Bit.get(in[cha[u][i]]) == Bit.get(in[u])) u = cha[u][i];
    } return u;
}

void solve() {
    cin >> n >> m >> Q;
    for(int i = 1; i <= n - 1; i ++) {
        int u, v; cin >> u >> v;
        ed[i] = { u, v, 0 };
        o[u].push_back(v), o[v].push_back(u);
    }
    dfs();
    for(int i = 1; i <= n - 1; i ++) {
        int &u = ed[i].u, &v = ed[i].v;
        if(cha[u][0] == v) swap(u, v);
        Bit.update(in[v], -1), Bit.update(out[v] + 1, +1);
    }

    for(int i = 1; i <= n; i ++) a[i] = 1, c[i] = 0;
    for(int _ = 1; _ <= m; _ ++) {
        int x; cin >> x;
        int u = ed[x].u, v = ed[x].v, &id = ed[x].id;
        if(id) { /// turn off now
            a[v] = c[v] = a[par(u)];
            Bit.update(in[v], -1), Bit.update(out[v] + 1, +1);
        }
        else { /// turn on now
            a[par(u)] += a[v] - c[v];
            Bit.update(in[v], +1), Bit.update(out[v] + 1, -1);
        }
        id ^= 1;
    }


    for(int i = 1; i <= Q; i ++) {
        int u; cin >> u;
        cout << a[par(u)] << '\n';
    }
}


int main() {
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --) {
        solve();
    }

    ctime();
    return 0;
}

Compilation message

synchronization.cpp: In function 'void iof()':
synchronization.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 10 ms 6748 KB Output is correct
8 Correct 10 ms 6860 KB Output is correct
9 Correct 10 ms 6724 KB Output is correct
10 Correct 100 ms 21944 KB Output is correct
11 Correct 108 ms 21840 KB Output is correct
12 Correct 161 ms 27988 KB Output is correct
13 Correct 57 ms 21960 KB Output is correct
14 Correct 73 ms 21328 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 24920 KB Output is correct
2 Correct 58 ms 24656 KB Output is correct
3 Correct 66 ms 27472 KB Output is correct
4 Correct 73 ms 27436 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5200 KB Output is correct
7 Correct 14 ms 7448 KB Output is correct
8 Correct 196 ms 28864 KB Output is correct
9 Correct 195 ms 28844 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 28844 KB Output is correct
2 Correct 103 ms 28500 KB Output is correct
3 Correct 115 ms 28752 KB Output is correct
4 Correct 105 ms 28756 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 2 ms 5140 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5184 KB Output is correct
6 Correct 13 ms 6936 KB Output is correct
7 Correct 139 ms 22868 KB Output is correct
8 Correct 193 ms 29012 KB Output is correct
9 Correct 64 ms 22984 KB Output is correct
10 Correct 88 ms 22568 KB Output is correct
11 Correct 76 ms 26116 KB Output is correct
12 Correct 79 ms 26196 KB Output is correct
13 Correct 123 ms 28752 KB Output is correct