oj.uz

Submission #855187

# Submission time Handle Problem Language Result Execution time Memory
855187 2023-09-30T13:25:01 Z ooscode Synchronization (JOI13_synchronization) C++17
100 / 100
 296 ms 41212 KB 
// IN THE NAME OF ALLAH
 
#include<bits/stdc++.h>
 
using namespace std;
 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define wall cerr << "------------------------------------" << endl
#define pb push_back
#define F first
#define S second
#define all(x) x.begin() , x.end()
#define int ll
#define kids int tm = (tl + tr)>>1; int cl = v<<1; int cr = v<<1|1
#define test int n; cin >> n; while(n--)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#pragma GCC optimize("Ofast")
 
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll , ll> pll;
 
const int N = 1e5 + 10;
const int K = 800+10;
const ll mod = 998244353;
const ll INF = 1e18+10;
const int P = 31;
const int lg = 25;

int fen[N];
int st[N] , fn[N] , tim;
int par[N][lg];
vector<int> g[N];
int n , m , q , v , u;
int ans[N] , lst[N];
int mark[N];
vector<pii> e;

void upd(int pos , int x) {
	while(pos <= n) {
		fen[pos] += x;
		pos += pos & -pos;
	}
} 

int ask(int pos) {
	int ans = 0;
	while(pos) {
		ans += fen[pos];
		pos -= pos & -pos;
	}
	return ans;
}

void dfs(int v) {
	st[v] = ++tim;
	for(auto u : g[v]) {
		if(u == par[v][0])
			continue;

		par[u][0] = v;
		dfs(u);
	}
	fn[v] = tim;

	upd(st[v] , 1); upd(fn[v] + 1 , -1);
}

void init() {
	for(int i = 1 ; i < lg ; i++)
		for(int v = 1 ; v <= n ; v++)	
			par[v][i] = par[par[v][i-1]][i-1];
}

int get(int v) {
	for(int i = lg-1 ; ~i ; i--) {
		if((par[v][i] != 0) && ask(st[par[v][i]]) == ask(st[v]))
			v = par[v][i];
	}
	return v;
}

void upd(int ind) {
	int v = e[ind-1].F;
	int u = e[ind-1].S;

	if(v == par[u][0])
		swap(u , v);

	if(!mark[ind]) {
		ans[get(u)] += ans[v] - lst[v];
		upd(st[v] , -1); upd(fn[v]+1 , 1);
		mark[ind] = 1;
		return;
	}

	lst[v] = ans[v] = ans[get(v)];
	upd(st[v] , 1); upd(fn[v]+1 , -1);
	mark[ind] = 0;
}

void solve() {
	fast;
	cin >> n >> m >> q;

	for(int i = 1 ; i <= n ; i++)
		ans[i] = 1;

	for(int i = 1 ; i < n ; i++) {
		int v , u;
		cin >> v >> u;
		g[v].pb(u);
		g[u].pb(v);
		e.pb({v , u});
	}

	dfs(1);
	init();

	while(m--) {
		int ind; cin >> ind;
		upd(ind);
	}

	while(q--) {
		int x;
		cin >> x;
		cout << ans[get(x)] << "\n";
	}
}

signed main()
{   
	solve();
} 

// IT'S EASY TO SEE
// CODE = LOVE

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6584 KB Output is correct
7 Correct 9 ms 9688 KB Output is correct
8 Correct 10 ms 9732 KB Output is correct
9 Correct 10 ms 9688 KB Output is correct
10 Correct 193 ms 34492 KB Output is correct
11 Correct 148 ms 34584 KB Output is correct
12 Correct 219 ms 40196 KB Output is correct
13 Correct 89 ms 34484 KB Output is correct
14 Correct 102 ms 33976 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 37060 KB Output is correct
2 Correct 77 ms 36832 KB Output is correct
3 Correct 87 ms 39616 KB Output is correct
4 Correct 87 ms 39612 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6568 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 15 ms 10364 KB Output is correct
8 Correct 296 ms 40964 KB Output is correct
9 Correct 266 ms 40896 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 41212 KB Output is correct
2 Correct 147 ms 40576 KB Output is correct
3 Correct 145 ms 40784 KB Output is correct
4 Correct 144 ms 40780 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 12 ms 9804 KB Output is correct
7 Correct 251 ms 35508 KB Output is correct
8 Correct 261 ms 40964 KB Output is correct
9 Correct 99 ms 35504 KB Output is correct
10 Correct 141 ms 35312 KB Output is correct
11 Correct 92 ms 38396 KB Output is correct
12 Correct 91 ms 38468 KB Output is correct
13 Correct 155 ms 40784 KB Output is correct