oj.uz

Submission #1093187

# Submission time Handle Problem Language Result Execution time Memory
1093187 2024-09-26T08:04:12 Z LucasLe Synchronization (JOI13_synchronization) C++17
100 / 100
 255 ms 43376 KB 
#include <bits/stdc++.h>
 
#define                int  long long
#define                pii  pair<int, int>
#define                 fi  first
#define                 se  second
#define                 ld  long double
#define                 vi  vector<int>
#define                vii  vector<vector<int>>
#define             all(v)  (v).begin(), (v).end()
#define       rep(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i)
#define       per(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
 
using namespace std;
 
const int MOD = 1e9 + 7;
 
int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
 
int mul(int a, int b) {
  (a *= b) %= MOD;
  return a;
}
 
int ceil(int x, int y) {
  return (x + y - 1) / y;
}
 
int bin_pow(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = res * x % MOD;
    x = x * x % MOD;
    y >>= 1;
  }
  return res;
}
 
template<class T> bool minimize(T& a, T b) {
  if (a > b) return a = b, true;
  return false;
}
 
template<class T> bool maximize(T& a, T b) {
  if (a < b) return a = b, true;
  return false;
}
 
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
 
const int INF = 1e17;
const int maxn = 2e5 + 5;
const int BASE = 1e6;
const int LG = 17;
 
int n, m, q, timeDfs;
int fen[maxn + 5];
int tin[maxn + 5], tout[maxn + 5];
int up[maxn + 5][LG + 5];
int h[maxn + 5], res[maxn + 5], data_save[maxn + 5];
 
vector<int> g[maxn + 5];
vector<pair<int, int>> edge(maxn + 5);
 
void dfs(int u, int p) {
	tin[u] = ++timeDfs;
	for (int v : g[u]) {
		if (v == p) continue;
		up[v][0] = u;
		h[v] = h[u] + 1;
		dfs(v, u);
	}
	tout[u] = timeDfs;
}
 
void upd(int v, int x) {
	for (; v <= n; v += v & (-v))
		fen[v] += x;
}
 
int get(int v) {
	int ans = 0;
	for (; v; v -= v & (-v))
		ans += fen[v];
	return ans;
}
 
int go_up(int u) {
	for (int j = LG; ~j; --j) {
		if ((1ll << j) > h[u]) continue;
		int p = up[u][j];
		if (h[u] - h[p] == get(tin[u]) - get(tin[p]))
			u = up[u][j];
	}
	return u;
}
 
void solve(int tc) {
	
	cin >> n >> m >> q;
	
	for (int i = 1; i < n; ++i) {
		cin >> edge[i].fi >> edge[i].se;
		g[edge[i].fi].push_back(edge[i].se);
		g[edge[i].se].push_back(edge[i].fi);
	}
	
	dfs(1, 0);
	up[1][0] = 1;
 
	for (int j = 1; j <= LG; ++j) 
		for (int i = 1; i <= n; ++i)
			up[i][j] = up[up[i][j - 1]][j - 1];
	
	for (int i = 1; i < n; ++i) {
		int u = edge[i].fi;
		int v = edge[i].se;
		if (h[u] > h[v]) 
			swap(edge[i].fi, edge[i].se);
	}
	
	vector<int> status(n + 1, 0);
	for (int i = 1; i <= n; ++i) res[i] = 1;
 
	for (int i = 1; i <= m; ++i) {
		
		int d; cin >> d;
		int u = edge[d].first, v = edge[d].second;
		int par = go_up(u);
		
		status[d] ^= 1;
		
		if (status[d]) {
			res[par] += res[v] - data_save[d];
			upd(tin[v], 1);
			upd(tout[v] + 1, -1);
		} else {
			res[v] = res[par];
			data_save[d] = res[par];
			upd(tin[v], -1);
			upd(tout[v] + 1, 1);
		}
	}
 
	for (int i = 1; i <= q; ++i) {
		int u; cin >> u;
		u = go_up(u);
		cout << res[u] << ' ';
	}
}
 
signed main() {
 
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
 
  int tc = 1;
  //cin >> tc;
 
  for (int i = 1; i <= tc; ++i) {
    solve(i);
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 4 ms 8168 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 10 ms 11140 KB Output is correct
8 Correct 13 ms 11096 KB Output is correct
9 Correct 12 ms 11100 KB Output is correct
10 Correct 120 ms 36992 KB Output is correct
11 Correct 142 ms 36948 KB Output is correct
12 Correct 198 ms 42576 KB Output is correct
13 Correct 58 ms 36804 KB Output is correct
14 Correct 105 ms 35676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 38984 KB Output is correct
2 Correct 62 ms 38612 KB Output is correct
3 Correct 115 ms 41304 KB Output is correct
4 Correct 95 ms 41304 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8280 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 3 ms 8348 KB Output is correct
4 Correct 4 ms 8284 KB Output is correct
5 Correct 4 ms 8308 KB Output is correct
6 Correct 4 ms 8536 KB Output is correct
7 Correct 21 ms 11804 KB Output is correct
8 Correct 255 ms 43376 KB Output is correct
9 Correct 249 ms 43280 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 43348 KB Output is correct
2 Correct 144 ms 42320 KB Output is correct
3 Correct 153 ms 42576 KB Output is correct
4 Correct 141 ms 42368 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 4 ms 8312 KB Output is correct
5 Correct 4 ms 8540 KB Output is correct
6 Correct 13 ms 11140 KB Output is correct
7 Correct 162 ms 37732 KB Output is correct
8 Correct 241 ms 43348 KB Output is correct
9 Correct 72 ms 37884 KB Output is correct
10 Correct 104 ms 36752 KB Output is correct
11 Correct 86 ms 40212 KB Output is correct
12 Correct 86 ms 40144 KB Output is correct
13 Correct 133 ms 42576 KB Output is correct