oj.uz

Submission #359248

# Submission time Handle Problem Language Result Execution time Memory
359248 2021-01-26T13:56:45 Z pure_mem Synchronization (JOI13_synchronization) C++14
100 / 100
 684 ms 23660 KB 
#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e5 + 12;

int n, m, q, tin[N], tout[N], timer, f[2 * N], lca[17][N];
int ans[N], last[N], dsu[N];
bool on[N];
pair<int, int> road[N];
vector<int> g[N];

int get(int v){
	int val = 0;
	for(;v >= 0;v = (v & (v + 1)) - 1)
		val += f[v];
	return val;
}

void upd(int v, int val){
	for(;v <= timer;v = v | (v + 1))
		f[v] += val;
}

void dfs(int v, int pr){
	lca[0][v] = pr, tin[v] = ++timer;
	for(int to: g[v]){
		if(to != pr)
			dfs(to, v);
	}
	tout[v] = ++timer;
}

int get_pr(int v){
	int kv = get(tin[v]);
	for(int i = 16;i >= 0;i--){
		if(kv == get(tin[lca[i][v]]))
			v = lca[i][v];
	}
	return v;
}

int main () {		
	scanf("%d %d %d", &n, &m, &q);
	for(int i = 1, x, y;i < n;i++){
		scanf("%d %d", &x, &y), road[i] = MP(x, y);
		g[x].push_back(y), g[y].push_back(x);
	}
	dfs(1, 1);
	for(int i = 1;i <= n;i++)
		ans[i] = 1, upd(tin[i], 1), upd(tout[i], -1);
	for(int i = 1;i <= 16;i++)
		for(int j = 1;j <= n;j++)
			lca[i][j] = lca[i - 1][lca[i - 1][j]];
	for(int v;m--;){
		scanf("%d", &v);	
		on[v] ^= 1;
		if(on[v]){
			int u = get_pr(lca[0][road[v].X] == road[v].Y ? road[v].Y: road[v].X);
			v = (lca[0][road[v].X] == road[v].Y ? road[v].X: road[v].Y);
			ans[u] = ans[u] + ans[v] - last[v];
			upd(tin[v], -1);
			upd(tout[v], 1);	
		}
		else{
			int u = get_pr(lca[0][road[v].X] == road[v].Y ? road[v].Y: road[v].X);
			v = (lca[0][road[v].X] == road[v].Y ? road[v].X: road[v].Y);
			ans[v] = last[v] = ans[u];
			upd(tin[v], 1);
			upd(tout[v], -1);	
		}
	}
	for(int v;q--;){
		scanf("%d", &v);
		printf("%d\n", ans[get_pr(v)]);
	}
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%d %d", &x, &y), road[i] = MP(x, y);
      |   ~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   scanf("%d", &v);
      |   ~~~~~^~~~~~~~~~
synchronization.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |   scanf("%d", &v);
      |   ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 2 ms 2796 KB Output is correct
6 Correct 4 ms 2924 KB Output is correct
7 Correct 20 ms 4332 KB Output is correct
8 Correct 20 ms 4332 KB Output is correct
9 Correct 21 ms 4460 KB Output is correct
10 Correct 496 ms 18156 KB Output is correct
11 Correct 541 ms 18156 KB Output is correct
12 Correct 570 ms 22892 KB Output is correct
13 Correct 133 ms 18020 KB Output is correct
14 Correct 310 ms 17132 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 20076 KB Output is correct
2 Correct 112 ms 19948 KB Output is correct
3 Correct 124 ms 21868 KB Output is correct
4 Correct 126 ms 21740 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2944 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 2 ms 2796 KB Output is correct
6 Correct 4 ms 2924 KB Output is correct
7 Correct 27 ms 4844 KB Output is correct
8 Correct 668 ms 23660 KB Output is correct
9 Correct 684 ms 23532 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 23660 KB Output is correct
2 Correct 213 ms 22892 KB Output is correct
3 Correct 202 ms 23020 KB Output is correct
4 Correct 197 ms 23020 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 3 ms 2796 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 4 ms 2924 KB Output is correct
6 Correct 26 ms 4460 KB Output is correct
7 Correct 629 ms 18940 KB Output is correct
8 Correct 662 ms 23532 KB Output is correct
9 Correct 193 ms 19184 KB Output is correct
10 Correct 332 ms 18424 KB Output is correct
11 Correct 160 ms 21228 KB Output is correct
12 Correct 159 ms 21228 KB Output is correct
13 Correct 229 ms 23020 KB Output is correct