oj.uz

Submission #410947

# Submission time Handle Problem Language Result Execution time Memory
410947 2021-05-24T00:21:36 Z JerryLiu06 Synchronization (JOI13_synchronization) C++17
100 / 100
 322 ms 24260 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using db = long double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)

const int MOD = 1e9 + 7;
const int MX = 1e5 + 10;
const ll INF = 1e18;

int N, M, Q, timer = 1; int U[MX], V[MX]; vi adj[MX]; bool active[MX];

int ans[MX], last[MX]; int in[MX], out[MX], lift[MX][20]; int BIT[MX];

// Preorder Traversal ~ O(N)

void DFS(int X, int P) {
    lift[X][0] = P; in[X] = timer++; ans[X] = 1;

    EACH(Y, adj[X]) if (Y != P) DFS(Y, X); out[X] = timer;
}
// Binary Indexed Tree

void update(int ind, int val) { while (ind <= timer) { BIT[ind] += val; ind += (ind & -ind); } }

int query(int ind) { int res = 0; while (ind > 0) { res += BIT[ind]; ind -= (ind & -ind); } return res; }

// Find the root of our connected component ~ O(lg^2 N)

int findRoot(int X) {
    R0F(i, 20) if (lift[X][i] && query(in[lift[X][i]]) == query(in[X])) X = lift[X][i]; return X;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> M >> Q; F0R(i, N - 1) { cin >> U[i] >> V[i]; adj[U[i]].pb(V[i]), adj[V[i]].pb(U[i]); }

    DFS(1, 0); FOR(j, 1, 20) FOR(i, 1, N + 1) lift[i][j] = lift[lift[i][j - 1]][j - 1];
    
    FOR(i, 1, N + 1) update(in[i], -1), update(out[i], 1);
    
    F0R(i, M) { int ind; cin >> ind; ind--;
        int X = U[ind], Y = V[ind]; if (lift[X][0] == Y) swap(X, Y); // X is par of Y

        if (active[ind]) {
            ans[Y] = last[Y] = ans[findRoot(Y)]; update(in[Y], -1), update(out[Y], 1);
        }
        if (!active[ind]) {
            update(in[Y], 1), update(out[Y], -1); ans[findRoot(Y)] += ans[Y] - last[Y];
        }
        active[ind] = !active[ind];
    }
    F0R(i, Q) { int X; cin >> X; cout << ans[findRoot(X)] << "\n"; }
}

Compilation message

synchronization.cpp: In function 'void DFS(int, int)':
synchronization.cpp:42:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   42 | #define EACH(a, x) for (auto& a : x)
      |                    ^~~
synchronization.cpp:57:5: note: in expansion of macro 'EACH'
   57 |     EACH(Y, adj[X]) if (Y != P) DFS(Y, X); out[X] = timer;
      |     ^~~~
synchronization.cpp:57:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   57 |     EACH(Y, adj[X]) if (Y != P) DFS(Y, X); out[X] = timer;
      |                                            ^~~
synchronization.cpp: In function 'int findRoot(int)':
synchronization.cpp:40:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   40 | #define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
      |                      ^~~
synchronization.cpp:41:19: note: in expansion of macro 'ROF'
   41 | #define R0F(i, a) ROF(i, 0, a)
      |                   ^~~
synchronization.cpp:68:5: note: in expansion of macro 'R0F'
   68 |     R0F(i, 20) if (lift[X][i] && query(in[lift[X][i]]) == query(in[X])) X = lift[X][i]; return X;
      |     ^~~
synchronization.cpp:68:89: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   68 |     R0F(i, 20) if (lift[X][i] && query(in[lift[X][i]]) == query(in[X])) X = lift[X][i]; return X;
      |                                                                                         ^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 4 ms 2764 KB Output is correct
7 Correct 15 ms 4172 KB Output is correct
8 Correct 14 ms 4292 KB Output is correct
9 Correct 15 ms 4292 KB Output is correct
10 Correct 210 ms 18752 KB Output is correct
11 Correct 217 ms 18756 KB Output is correct
12 Correct 251 ms 23420 KB Output is correct
13 Correct 123 ms 18744 KB Output is correct
14 Correct 145 ms 17892 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 20692 KB Output is correct
2 Correct 96 ms 20436 KB Output is correct
3 Correct 120 ms 22536 KB Output is correct
4 Correct 115 ms 22468 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 4 ms 2892 KB Output is correct
7 Correct 22 ms 4832 KB Output is correct
8 Correct 313 ms 24196 KB Output is correct
9 Correct 322 ms 24260 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 24196 KB Output is correct
2 Correct 194 ms 23548 KB Output is correct
3 Correct 185 ms 23676 KB Output is correct
4 Correct 184 ms 23656 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 19 ms 4304 KB Output is correct
7 Correct 288 ms 19704 KB Output is correct
8 Correct 313 ms 24212 KB Output is correct
9 Correct 145 ms 19836 KB Output is correct
10 Correct 180 ms 19268 KB Output is correct
11 Correct 133 ms 21924 KB Output is correct
12 Correct 132 ms 21828 KB Output is correct
13 Correct 185 ms 23696 KB Output is correct