oj.uz

Submission #768831

# Submission time Handle Problem Language Result Execution time Memory
768831 2023-06-28T17:39:35 Z fanwen Synchronization (JOI13_synchronization) C++17
100 / 100
 251 ms 24956 KB 
/**
 *      author : pham van sam 
 *      created : 28 June 2023 (Wednesday)
 **/

#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

template <typename U, typename V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <typename U, typename V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }

void you_make_it(void);

signed main() {

    #define TASK "synchronization"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    auto start_time = chrono::steady_clock::now();

    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; ++i) {
        you_make_it();
        // cout << '\n';
    }

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

template <class T> struct Fenwick_Tree {
    vector<T> bit;
    int n;
    Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5){}
    
    void clear() { fill(bit.begin(), bit.end(), T(0)); }

    void update(int u, T val) {
        for (; u <= n; u += u & -u) bit[u] += val;
    }
    
    T get(int u) {
        T ans = 0;
        for (; u; u -= u & -u) ans += bit[u];
        return ans; 
    }
    
    T get(int l, int r) {
        return get(r) - get(l - 1);
    }
};

const int MAXN = 1e5 + 2;

Fenwick_Tree <int> bit;

int N, M, Q, anc[MAXN][21], active[MAXN];
vector <int> adj[MAXN];
int infor[MAXN], last_sync[MAXN];
pair <int, int> edges[MAXN];
int time_in[MAXN], time_out[MAXN];

void dfs(int u, int p) {
    anc[u][0] = p;
    FOR(i, 1, 20) anc[u][i] = anc[anc[u][i - 1]][i - 1];
    static int run = 0;
    infor[u] = 1;
    time_in[u] = ++run;
    for (auto v : adj[u]) if(v != p) dfs(v, u);
    time_out[u] = run;
}

int find_anc(int u) {
    int lca = u;
    FORD(i, 20, 0) if(anc[lca][i] != 0 && bit.get(time_in[anc[lca][i]]) == bit.get(time_in[u])) {
        lca = anc[lca][i];
    }
    return lca;
}

void you_make_it() {
    cin >> N >> M >> Q;
    FOR(i, 1, N - 1) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges[i] = make_pair(u, v);
    }
    dfs(1, 0);
    bit = Fenwick_Tree <int> (N);
    FOR(i, 1, N) {
        bit.update(time_in[i], -1);
        bit.update(time_out[i] + 1, 1);
    }
    while(M--) {
        int x; cin >> x;
        auto [u, v] = edges[x];
        if(anc[u][0] == v) swap(u, v);
        if(active[x]) {
            infor[v] = last_sync[v] = infor[find_anc(u)];
            bit.update(time_in[v], -1);
            bit.update(time_out[v] + 1, 1);
        } else {
            infor[find_anc(u)] += infor[v] - last_sync[v];
            bit.update(time_in[v], 1);
            bit.update(time_out[v] + 1, -1);
        }
        active[x] = !active[x];
    }

    while(Q--) {
        int x; cin >> x;
        cout << infor[find_anc(x)] << '\n';
    }
}

// Dream it. Wish it. Do it.

Compilation message

synchronization.cpp: In instantiation of 'Fenwick_Tree<T>::Fenwick_Tree(int) [with T = int]':
synchronization.cpp:73:20:   required from here
synchronization.cpp:51:9: warning: 'Fenwick_Tree<int>::n' will be initialized after [-Wreorder]
   51 |     int n;
      |         ^
synchronization.cpp:50:15: warning:   'std::vector<int> Fenwick_Tree<int>::bit' [-Wreorder]
   50 |     vector<T> bit;
      |               ^~~
synchronization.cpp:52:5: warning:   when initialized here [-Wreorder]
   52 |     Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5){}
      |     ^~~~~~~~~~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 10 ms 4364 KB Output is correct
8 Correct 10 ms 4236 KB Output is correct
9 Correct 10 ms 4356 KB Output is correct
10 Correct 140 ms 19532 KB Output is correct
11 Correct 145 ms 19504 KB Output is correct
12 Correct 163 ms 24104 KB Output is correct
13 Correct 59 ms 19452 KB Output is correct
14 Correct 100 ms 18648 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 21332 KB Output is correct
2 Correct 66 ms 21124 KB Output is correct
3 Correct 80 ms 23244 KB Output is correct
4 Correct 80 ms 23232 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 3 ms 2824 KB Output is correct
7 Correct 17 ms 4852 KB Output is correct
8 Correct 207 ms 24944 KB Output is correct
9 Correct 201 ms 24940 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 24956 KB Output is correct
2 Correct 129 ms 24276 KB Output is correct
3 Correct 128 ms 24392 KB Output is correct
4 Correct 128 ms 24392 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 13 ms 4436 KB Output is correct
7 Correct 156 ms 20412 KB Output is correct
8 Correct 251 ms 24908 KB Output is correct
9 Correct 83 ms 20856 KB Output is correct
10 Correct 113 ms 19808 KB Output is correct
11 Correct 91 ms 22544 KB Output is correct
12 Correct 89 ms 22604 KB Output is correct
13 Correct 122 ms 24336 KB Output is correct