oj.uz

Submission #1084900

# Submission time Handle Problem Language Result Execution time Memory
1084900 2024-09-07T07:50:13 Z Sunbae Synchronization (JOI13_synchronization) C++17
100 / 100
 213 ms 23388 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
using namespace std;
using pii = pair<int,int>;
const int N = 1e5 + 5;
vector<int> g[N];
pii e[N], A[N];
int timer, tin[N], tout[N], up[N][17], bit[N<<1], LOG;
bool active[N];
void upd(int i, int val){ for(; i<(N<<1); i+=i&-i) bit[i] += val;}
int qry(int i){ int res = 0; for(; i; i-=i&-i) res += bit[i]; return res;}
void dfs(int u, int p){
	up[u][0] = p; tin[u] = timer++;
	for(int j = 1; j<LOG; ++j) up[u][j] = up[up[u][j-1]][j-1];
	for(int v : g[u]) if(v != p) dfs(v, u);
	tout[u] = timer++;	
}

int find_root(int u){
	int v = u, qry_u = qry(tin[u]);
	for(int j = LOG-1; j>=0; --j) if(qry(tin[up[v][j]]) == qry_u) v = up[v][j];
	return v;
}

signed main(){
	int n, m, q; scanf("%d %d %d", &n, &m, &q); LOG = 32 - __builtin_clz(n);
	for(int i = 0, u, v; i<n-1; ++i){
		scanf("%d %d", &u, &v); --u; --v;
		g[u].push_back(v); g[v].push_back(u);
		e[i] = mp(u, v);
	}
	timer = 1; dfs(0, 0);
	for(int i= 0; i<n-1; ++i){
		int u = e[i].F, v = e[i].S; if(tin[u] > tin[v]) swap(u, v);
		upd(tin[v], +1); upd(tout[v], -1);
	}
	fill(A, A+n, mp(1, 0));
	for(int i = 0; i<m; ++i){
		int j; scanf("%d", &j); --j;
		int u = e[j].F, v = e[j].S; if(tin[u] > tin[v]) swap(u, v);
		if(active[j]){ //remove
			A[v] = mp(A[find_root(u)].F, A[find_root(u)].F);
			upd(tin[v], +1); upd(tout[v], -1);
		}else{ //add
			A[find_root(u)].F += A[v].F - A[v].S;
			upd(tin[v], -1); upd(tout[v], +1);
		}
		active[j] ^= 1;
	}
	for(int u; q--; ) scanf("%d", &u), printf("%d\n", A[find_root(--u)].F);
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:28:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  int n, m, q; scanf("%d %d %d", &n, &m, &q); LOG = 32 - __builtin_clz(n);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%d %d", &u, &v); --u; --v;
      |   ~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:41:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   int j; scanf("%d", &j); --j;
      |          ~~~~~^~~~~~~~~~
synchronization.cpp:52:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  for(int u; q--; ) scanf("%d", &u), printf("%d\n", A[find_root(--u)].F);
      |                    ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.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 2 ms 2788 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 11 ms 4152 KB Output is correct
8 Correct 10 ms 4336 KB Output is correct
9 Correct 11 ms 4188 KB Output is correct
10 Correct 128 ms 17940 KB Output is correct
11 Correct 134 ms 18000 KB Output is correct
12 Correct 181 ms 22632 KB Output is correct
13 Correct 79 ms 17864 KB Output is correct
14 Correct 83 ms 17488 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 20308 KB Output is correct
2 Correct 78 ms 20048 KB Output is correct
3 Correct 85 ms 22096 KB Output is correct
4 Correct 73 ms 22096 KB Output is correct

Subtask #3
10.0 / 10.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 1 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 16 ms 4824 KB Output is correct
8 Correct 207 ms 23324 KB Output is correct
9 Correct 206 ms 23376 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 23376 KB Output is correct
2 Correct 122 ms 22996 KB Output is correct
3 Correct 126 ms 23376 KB Output is correct
4 Correct 114 ms 23204 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 2 ms 2788 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 13 ms 4384 KB Output is correct
7 Correct 168 ms 19028 KB Output is correct
8 Correct 213 ms 23388 KB Output is correct
9 Correct 102 ms 19028 KB Output is correct
10 Correct 123 ms 18696 KB Output is correct
11 Correct 109 ms 21332 KB Output is correct
12 Correct 108 ms 21492 KB Output is correct
13 Correct 111 ms 23360 KB Output is correct