oj.uz

Submission #972910

# Submission time Handle Problem Language Result Execution time Memory
972910 2024-05-01T10:12:00 Z dio_2 Synchronization (JOI13_synchronization) C++17
100 / 100
 295 ms 30700 KB 
#include<bits/stdc++.h>
using namespace std;

struct FenwickTree{
    vector<long long> fenw;
    int n;
    
    FenwickTree () {}
    
    FenwickTree (int siz){
		init(siz);
	}
    
    void init(int siz){
        n = siz;
        fenw.assign(n, 0);
    }
    \
    long long sum(int r){
        long long res = 0;
        while(r >= 0){
            res += fenw[r];
            r = (r & (r + 1)) - 1;
        }
        return res;
    }
    
    long long sum(int l, int r){
        long long res = sum(r);
        if(l) res -= sum(l - 1);
        return res;
    }
    
    void add(int where, long long val){
        while(where < n){
            fenw[where] += val;
            where |= (where + 1);
        }
    }
    
    void set(int where, long long val){
        long long cr = sum(where, where);
        add(where, -cr + val);
    }
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, q;
	cin >> n >> m >> q;
	
	vector<vector<int>> g(n + 1);
	vector<pair<int, int>> kraw(n);
	vector<int> state_kraw(n); // na poczatky wszytko jest off.
	
	for(int i = 0;i < n - 1;i++){
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
		kraw[i + 1] = make_pair(a, b);
	}
	
	vector<int> dep(n + 1), tin(n + 1), tout(n + 1);
	vector<int> parent(n + 1), parent_kraw(n + 1);
	vector<int> passed_cnt(n + 1); // ile przeszlo od danej krawedzi
	vector<int> info(n + 1, 1); // ile informacij ma dane korzenie ( czyli leader DSU )
	
	const int LOG = 20;
	vector<vector<int>> up(n + 1, vector<int> (LOG, 1));
	FenwickTree fen(2 * n + 2); 
	// 1) query me to root it is (1, in[u])
	// 2) update my weight is +w on in[u], -w on out[u]. :)

	int T = 1;
	auto dfs1 = [&](auto &&dfs1, int u, int p)->void{
		tin[u] = T++;
		for(int v : g[u]) if(v != p){
			parent[v] = u;
			dep[v] = dep[u] + 1;
			up[v][0] = u;
			for(int i = 1;i < LOG;i++) up[v][i] = up[ up[v][i - 1] ][i - 1];
			dfs1(dfs1, v, u);
		}
		tout[u] = T++;
	}; dfs1(dfs1, 1, 0);
	
	auto lca = [&](int a, int b)->int{
		assert(a != b); // its just that i won't be doing such queries
		if(dep[a] > dep[b]) swap(a, b);
		int diff = dep[b] - dep[a];
		for(int i = LOG - 1;i >= 0;i--){
			if((diff >> i) & 1){
				b = up[b][i];
			}
		}
		assert(dep[b] == dep[a]);
		if(a == b) return a;
		for(int i = LOG - 1;i >= 0;i--){
			if(up[a][i] != up[b][i]){
				a = up[a][i];
				b = up[b][i];
			}
		}
		return up[a][0];
	};
	
	for(int i = 1;i <= n - 1;i++){
		auto [a, b] = kraw[i];
		if(dep[a] > dep[b]) swap(a, b);
		parent_kraw[b] = i;
	}
	
	auto isAnc = [&](int a, int b)->bool{
		return tin[a] <= tin[b] and tout[b] <= tout[a];
	};
	
	auto isOnPath = [&](int a, int b)->int{
		if(dep[a] > dep[b]) swap(a, b);
		assert(isAnc(a, b));
		int dA = fen.sum(1, tin[a]);
		int dB = fen.sum(1, tin[b]);
		return dep[b] - dep[a] == dB - dA;
	};
	
	auto go_up = [&](int &a)->void{
		for(int j = LOG - 1;j >= 0;j--){
			if(isOnPath(a, up[a][j])){
				a = up[a][j];
			}
		}
	};
	
	while(m--){
		int e;
		cin >> e;
		
		auto [a, b] = kraw[e];
		if(dep[a] > dep[b]) swap(a, b);
		// a na gorze
		
		if(!state_kraw[e]){ // polacz 
			// b jest korzeniem dolnego poddrzewa
			// dla a nie wiemy kim jest leaderem treba isc do gory do poki mozna
			//~ while(parent[a] and state_kraw[ parent_kraw[a] ] ) a = parent[a]; // this is the SLOW.
			fen.set(tin[b], 1);
			fen.set(tout[b], -1); // you update deeper.
			go_up(a);
			int przejdzie = info[b] - passed_cnt[e];
			info[a] += przejdzie;
			passed_cnt[e] += przejdzie;
		} else { // rozlacz
			//~ while(parent[a] and state_kraw[ parent_kraw[a] ] ) a = parent[a]; // SLOW 
			go_up(a);
			fen.set(tin[b], 0);
			fen.set(tout[b], 0);
			passed_cnt[e] = info[a];
			info[b] = info[a];
		}
		
		state_kraw[e] ^= 1;
	}
	
	for(int i = 0;i < q;i++){
		int a;
		cin >> a;
		//~ while(parent[a] and state_kraw[ parent_kraw[a] ] ) a = parent[a]; // SLOW  
		go_up(a);
		cout << info[a] << '\n';                              
	}
	
	return 0;	
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:90:7: warning: variable 'lca' set but not used [-Wunused-but-set-variable]
   90 |  auto lca = [&](int a, int b)->int{
      |       ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 14 ms 2904 KB Output is correct
8 Correct 14 ms 2908 KB Output is correct
9 Correct 13 ms 2908 KB Output is correct
10 Correct 196 ms 25424 KB Output is correct
11 Correct 245 ms 25624 KB Output is correct
12 Correct 216 ms 29520 KB Output is correct
13 Correct 96 ms 25292 KB Output is correct
14 Correct 154 ms 25048 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 27476 KB Output is correct
2 Correct 91 ms 27084 KB Output is correct
3 Correct 106 ms 28932 KB Output is correct
4 Correct 111 ms 29216 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 18 ms 3412 KB Output is correct
8 Correct 274 ms 30700 KB Output is correct
9 Correct 280 ms 30332 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 30268 KB Output is correct
2 Correct 162 ms 29912 KB Output is correct
3 Correct 159 ms 30292 KB Output is correct
4 Correct 175 ms 30540 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 18 ms 2908 KB Output is correct
7 Correct 270 ms 26196 KB Output is correct
8 Correct 284 ms 30336 KB Output is correct
9 Correct 129 ms 26572 KB Output is correct
10 Correct 171 ms 26444 KB Output is correct
11 Correct 123 ms 28664 KB Output is correct
12 Correct 117 ms 28496 KB Output is correct
13 Correct 162 ms 30216 KB Output is correct