oj.uz

Submission #1093194

# Submission time Handle Problem Language Result Execution time Memory
1093194 2024-09-26T08:33:02 Z LucasLe Synchronization (JOI13_synchronization) C++17
100 / 100
 252 ms 43468 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;

// thay vì ta lưu thông tin trên các nút đang liên thông nhau thì ta chỉ cần lưu trên một nút cố định là đc
// đây là một trick để lưu

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 3 ms 8284 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 3 ms 8312 KB Output is correct
4 Correct 3 ms 8328 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 4 ms 8580 KB Output is correct
7 Correct 11 ms 11100 KB Output is correct
8 Correct 10 ms 11100 KB Output is correct
9 Correct 11 ms 11100 KB Output is correct
10 Correct 115 ms 36964 KB Output is correct
11 Correct 124 ms 36944 KB Output is correct
12 Correct 203 ms 42568 KB Output is correct
13 Correct 62 ms 36860 KB Output is correct
14 Correct 95 ms 35616 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 38940 KB Output is correct
2 Correct 82 ms 38524 KB Output is correct
3 Correct 102 ms 41296 KB Output is correct
4 Correct 104 ms 41300 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 4 ms 8120 KB Output is correct
3 Correct 3 ms 8296 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 16 ms 11796 KB Output is correct
8 Correct 247 ms 43344 KB Output is correct
9 Correct 245 ms 43348 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 43468 KB Output is correct
2 Correct 137 ms 42320 KB Output is correct
3 Correct 141 ms 42576 KB Output is correct
4 Correct 141 ms 42528 KB Output is correct

Subtask #5
40.0 / 40.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 3 ms 8160 KB Output is correct
5 Correct 4 ms 8540 KB Output is correct
6 Correct 13 ms 11252 KB Output is correct
7 Correct 153 ms 37876 KB Output is correct
8 Correct 250 ms 43344 KB Output is correct
9 Correct 71 ms 37828 KB Output is correct
10 Correct 99 ms 36944 KB Output is correct
11 Correct 94 ms 40144 KB Output is correct
12 Correct 88 ms 40148 KB Output is correct
13 Correct 155 ms 42580 KB Output is correct