oj.uz

Submission #575990

# Submission time Handle Problem Language Result Execution time Memory
575990 2022-06-12T02:47:07 Z jiahng Inside information (BOI21_servers) C++14
100 / 100
 684 ms 144824 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
//~ #define ll int
#define int ll
typedef pair<int32_t, int32_t> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 120001
#define INF 1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;

int N,K;
vpi adj[maxn];
int sz[maxn], lvl[maxn],par[maxn][30];
void find_sz(int x, int p){
	sz[x] = 1;
	aFOR(i,adj[x]) if (i.f != p && lvl[i.f] == -1){
		find_sz(i.f,x); sz[x] += sz[i.f];
	}
}
int find_cent(int x,int p, int m){
	aFOR(i,adj[x]) if (i.f != p && lvl[i.f] == -1 && sz[i.f] > m / 2) return find_cent(i.f,x,m);
	return x;
}

bool inc[maxn][30], _dec[maxn][30];
int fi[maxn][30], la[maxn][30]; // All are measured top-down
void find_vals(int x, int p, int d, int incv, int decv, int first_edge, int last_edge){
	inc[x][d] = (incv != -1);
	_dec[x][d] = (decv != -1);
	fi[x][d] = first_edge;
	la[x][d] = last_edge;
	aFOR(i,adj[x]) if (i.f != p && lvl[i.f] == -1){
		int nincv, ndecv, nfirst_edge;
		if (incv == -1 || i.s < incv) nincv = -1;
		else nincv = i.s;
		
		if (decv == -1 || i.s > decv) ndecv = -1;
		else ndecv = i.s;
		
		if (first_edge == -1) nfirst_edge = i.s;
		else nfirst_edge = first_edge;
		
		find_vals(i.f, x, d, nincv, ndecv, nfirst_edge, i.s); 
	}
}
void decomp(int x,int p,int d){
	find_sz(x, -1);
	int cent = find_cent(x, -1, sz[x]);
	lvl[cent] = d;
	//~ cout << p << ' ' << cent << '\n';
	par[cent][d] = cent;
	FOR(i,0,d-1) par[cent][i] = par[p][i];
	
	find_vals(cent, -1, d, 0, N+1, -1, -1);
	
	aFOR(i,adj[cent]) if (lvl[i.f] == -1) decomp(i.f,cent, d+1);
}

char ch;
int a,b;


vi A[maxn];

struct FW{
	int N;
	vi fw, vect;
	int sm = 0;

	void add_pos(int x){
		vect.pb(x);
	}
	void init(){
		sort(all(vect)); vect.erase(unique(all(vect)), vect.end());
		fw = vi(vect.size()+1,0);
		N = vect.size();
	}
	void upd(int p,int v){
		p = lbd(vect, p) - vect.begin() + 1;
		assert(p > 0);
		sm += v;
		for (int i = p; i <= N; i += i & (-i)) fw[i] += v;
	}
	int qry(int p){
		p = lbd(vect, p) - vect.begin() + 1;
		int ans = 0;
		for (int i = p; i > 0; i -= i & (-i)) ans += fw[i];
		return ans;
	}
}fw[maxn];
int32_t main(){
    fast;
    cin >> N >> K;
    int co = 1;
    
    vector <pii> queries;
    
    FOR(i,1,N+K-1){
		cin >> ch;
		
		if (ch == 'S'){
			cin >> a >> b;
			adj[a].pb(pi(b, co)); adj[b].pb(pi(a,co));
			co++;
		}else if (ch == 'Q'){
			cin >> a >> b;
			queries.pb(pii(pi(a,b), co-1));
		}else{
			cin >> a;
			queries.pb(pii(pi(a, -1), co-1));
		}
	}
	mem(lvl, -1);
	mem(par, -1);
	decomp(1,-1,0);
	
	FOR(i,1,N) fw[i] = FW();
	FOR(i,1,N){
		FOR(j,0,29) if (par[i][j] != -1 && par[i][j] != i && inc[i][j]){
			A[par[i][j]].pb(i);
			fw[par[i][j]].add_pos(fi[i][j]);
		}
	}
	FOR(i,1,N) fw[i].init();
	FOR(i,1,N){
		sort(all(A[i]), [i](int x,int y){
			return la[x][lvl[i]] > la[y][lvl[i]];
		});
	}
	
	aFOR(i,queries){
		if (i.f.s != -1){
			int x = i.f.s, y = i.f.f;
			if (x == y){
				cout << "yes\n"; continue;
			}
			int lca = 0;
			DEC(d,29,0) if (par[x][d] != -1 && par[x][d] == par[y][d]){
				lca = d;
				break;
			}
			//~ cout << lca << ' ';
			if (_dec[x][lca] && inc[y][lca]){
				if (fi[x][lca] == -1 || fi[y][lca] == -1 || 
					fi[x][lca] < fi[y][lca]){
					
					int last = la[y][lca];
					if (lvl[y] == lca) last = fi[x][lca];
					if (last <= i.s){
						cout << "yes\n"; continue;
					}
				}
			}
			cout << "no\n";
		}else{
			int x = i.f.f;

			// For each lca depth d,
			// Find number of y fulfilling the conditions:
			//
			// _dec[x][d] (trivial)
			// inc[y][d] (Keep in vector A[par[y][d]])
			// fi[x][d] < fi[y][d] (Keep in fenwick
			// la[y][d] <= i.s (Vector from inc feeds into a fenwick for this)
			int ans = 0;
			DEC(d,lvl[x],0) if (_dec[x][d]){
				int z = par[x][d];
				while (!A[z].empty() && la[A[z].back()][d] <= i.s){
					int a = A[z].back();
					fw[z].upd(fi[a][d], 1);
					A[z].pop_back();
				}
				if (d == lvl[x]) ans += fw[z].sm;
				else ans += fw[z].sm - fw[z].qry(fi[x][d]);
				
				//~ if (x != z){ // y == z case
					if (_dec[x][d] && fi[x][d] <= i.s) ans++;
				//~ }
			}
			
			cout << ans << '\n';
		}
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 45328 KB Output is correct
2 Correct 59 ms 47588 KB Output is correct
3 Correct 55 ms 47528 KB Output is correct
4 Correct 50 ms 47636 KB Output is correct
5 Correct 51 ms 47736 KB Output is correct
6 Correct 45 ms 47536 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 45328 KB Output is correct
2 Correct 59 ms 47588 KB Output is correct
3 Correct 55 ms 47528 KB Output is correct
4 Correct 50 ms 47636 KB Output is correct
5 Correct 51 ms 47736 KB Output is correct
6 Correct 45 ms 47536 KB Output is correct
7 Correct 40 ms 45120 KB Output is correct
8 Correct 56 ms 48516 KB Output is correct
9 Correct 55 ms 48608 KB Output is correct
10 Correct 56 ms 48644 KB Output is correct
11 Correct 54 ms 48604 KB Output is correct
12 Correct 53 ms 48568 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 45292 KB Output is correct
2 Correct 196 ms 120560 KB Output is correct
3 Correct 207 ms 120720 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 45292 KB Output is correct
2 Correct 196 ms 120560 KB Output is correct
3 Correct 207 ms 120720 KB Output is correct
4 Correct 41 ms 45260 KB Output is correct
5 Correct 239 ms 123200 KB Output is correct
6 Correct 193 ms 122464 KB Output is correct
7 Correct 206 ms 122544 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 45236 KB Output is correct
2 Correct 315 ms 129644 KB Output is correct
3 Correct 337 ms 129528 KB Output is correct
4 Correct 265 ms 142340 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 45236 KB Output is correct
2 Correct 315 ms 129644 KB Output is correct
3 Correct 337 ms 129528 KB Output is correct
4 Correct 265 ms 142340 KB Output is correct
5 Correct 47 ms 45048 KB Output is correct
6 Correct 360 ms 132196 KB Output is correct
7 Correct 336 ms 144628 KB Output is correct
8 Correct 354 ms 131836 KB Output is correct
9 Correct 419 ms 131852 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 45248 KB Output is correct
2 Correct 294 ms 133004 KB Output is correct
3 Correct 286 ms 123576 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 45248 KB Output is correct
2 Correct 294 ms 133004 KB Output is correct
3 Correct 286 ms 123576 KB Output is correct
4 Correct 42 ms 45080 KB Output is correct
5 Correct 321 ms 135716 KB Output is correct
6 Correct 357 ms 126356 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 45276 KB Output is correct
2 Correct 345 ms 129484 KB Output is correct
3 Correct 313 ms 129552 KB Output is correct
4 Correct 270 ms 142388 KB Output is correct
5 Correct 42 ms 45052 KB Output is correct
6 Correct 252 ms 133016 KB Output is correct
7 Correct 281 ms 123724 KB Output is correct
8 Correct 427 ms 123996 KB Output is correct
9 Correct 375 ms 123996 KB Output is correct
10 Correct 452 ms 131612 KB Output is correct
11 Correct 465 ms 131624 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 45276 KB Output is correct
2 Correct 345 ms 129484 KB Output is correct
3 Correct 313 ms 129552 KB Output is correct
4 Correct 270 ms 142388 KB Output is correct
5 Correct 42 ms 45052 KB Output is correct
6 Correct 252 ms 133016 KB Output is correct
7 Correct 281 ms 123724 KB Output is correct
8 Correct 427 ms 123996 KB Output is correct
9 Correct 375 ms 123996 KB Output is correct
10 Correct 452 ms 131612 KB Output is correct
11 Correct 465 ms 131624 KB Output is correct
12 Correct 39 ms 45140 KB Output is correct
13 Correct 340 ms 132268 KB Output is correct
14 Correct 334 ms 144824 KB Output is correct
15 Correct 361 ms 131804 KB Output is correct
16 Correct 409 ms 131896 KB Output is correct
17 Correct 40 ms 45768 KB Output is correct
18 Correct 326 ms 135884 KB Output is correct
19 Correct 308 ms 126332 KB Output is correct
20 Correct 400 ms 126740 KB Output is correct
21 Correct 402 ms 126828 KB Output is correct
22 Correct 545 ms 134140 KB Output is correct
23 Correct 684 ms 141608 KB Output is correct
24 Correct 629 ms 141032 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 45452 KB Output is correct
2 Correct 56 ms 47640 KB Output is correct
3 Correct 50 ms 47672 KB Output is correct
4 Correct 54 ms 47724 KB Output is correct
5 Correct 50 ms 47836 KB Output is correct
6 Correct 51 ms 47712 KB Output is correct
7 Correct 42 ms 45228 KB Output is correct
8 Correct 206 ms 120772 KB Output is correct
9 Correct 202 ms 120656 KB Output is correct
10 Correct 43 ms 45180 KB Output is correct
11 Correct 311 ms 129592 KB Output is correct
12 Correct 349 ms 129704 KB Output is correct
13 Correct 261 ms 142480 KB Output is correct
14 Correct 54 ms 45156 KB Output is correct
15 Correct 268 ms 133136 KB Output is correct
16 Correct 283 ms 123808 KB Output is correct
17 Correct 358 ms 124140 KB Output is correct
18 Correct 347 ms 124120 KB Output is correct
19 Correct 470 ms 131756 KB Output is correct
20 Correct 484 ms 131780 KB Output is correct
21 Correct 228 ms 121600 KB Output is correct
22 Correct 220 ms 121344 KB Output is correct
23 Correct 321 ms 123612 KB Output is correct
24 Correct 275 ms 123744 KB Output is correct
25 Correct 519 ms 127560 KB Output is correct
26 Correct 361 ms 122552 KB Output is correct
27 Correct 352 ms 122492 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 45452 KB Output is correct
2 Correct 56 ms 47640 KB Output is correct
3 Correct 50 ms 47672 KB Output is correct
4 Correct 54 ms 47724 KB Output is correct
5 Correct 50 ms 47836 KB Output is correct
6 Correct 51 ms 47712 KB Output is correct
7 Correct 42 ms 45228 KB Output is correct
8 Correct 206 ms 120772 KB Output is correct
9 Correct 202 ms 120656 KB Output is correct
10 Correct 43 ms 45180 KB Output is correct
11 Correct 311 ms 129592 KB Output is correct
12 Correct 349 ms 129704 KB Output is correct
13 Correct 261 ms 142480 KB Output is correct
14 Correct 54 ms 45156 KB Output is correct
15 Correct 268 ms 133136 KB Output is correct
16 Correct 283 ms 123808 KB Output is correct
17 Correct 358 ms 124140 KB Output is correct
18 Correct 347 ms 124120 KB Output is correct
19 Correct 470 ms 131756 KB Output is correct
20 Correct 484 ms 131780 KB Output is correct
21 Correct 228 ms 121600 KB Output is correct
22 Correct 220 ms 121344 KB Output is correct
23 Correct 321 ms 123612 KB Output is correct
24 Correct 275 ms 123744 KB Output is correct
25 Correct 519 ms 127560 KB Output is correct
26 Correct 361 ms 122552 KB Output is correct
27 Correct 352 ms 122492 KB Output is correct
28 Correct 42 ms 45276 KB Output is correct
29 Correct 74 ms 48528 KB Output is correct
30 Correct 57 ms 48540 KB Output is correct
31 Correct 56 ms 48592 KB Output is correct
32 Correct 60 ms 48652 KB Output is correct
33 Correct 50 ms 48564 KB Output is correct
34 Correct 39 ms 45796 KB Output is correct
35 Correct 242 ms 123184 KB Output is correct
36 Correct 196 ms 122576 KB Output is correct
37 Correct 196 ms 122528 KB Output is correct
38 Correct 50 ms 45812 KB Output is correct
39 Correct 356 ms 132288 KB Output is correct
40 Correct 368 ms 144724 KB Output is correct
41 Correct 397 ms 131808 KB Output is correct
42 Correct 376 ms 131768 KB Output is correct
43 Correct 46 ms 45868 KB Output is correct
44 Correct 338 ms 135800 KB Output is correct
45 Correct 347 ms 126324 KB Output is correct
46 Correct 444 ms 126668 KB Output is correct
47 Correct 422 ms 126880 KB Output is correct
48 Correct 556 ms 134092 KB Output is correct
49 Correct 678 ms 141628 KB Output is correct
50 Correct 625 ms 141328 KB Output is correct
51 Correct 224 ms 124600 KB Output is correct
52 Correct 199 ms 123428 KB Output is correct
53 Correct 228 ms 122960 KB Output is correct
54 Correct 194 ms 123632 KB Output is correct
55 Correct 211 ms 123492 KB Output is correct
56 Correct 276 ms 126388 KB Output is correct
57 Correct 418 ms 129800 KB Output is correct
58 Correct 438 ms 125092 KB Output is correct
59 Correct 368 ms 125488 KB Output is correct