oj.uz

Submission #523448

# Submission time Handle Problem Language Result Execution time Memory
523448 2022-02-07T16:27:44 Z fatemetmhr Inside information (BOI21_servers) C++17
50 / 100
 281 ms 48372 KB 
// Be name khoda! //
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn5 = 3e5 + 10;
const int lg    = 20;

#define pb    push_back

int par[lg + 1][maxn5], mn1[maxn5], mn2[maxn5];
vector <pair<int, int>> adj[maxn5];
int h[maxn5], a[maxn5], b[maxn5], paredge[maxn5];
char ty[maxn5];

inline void dfs(int v, int lim1, int lim2){
	for(int i = 1; i < lg && par[i - 1][v] != -1; i++)
		par[i][v] = par[i - 1][par[i - 1][v]];
	for(auto [u, i] : adj[v]) if(u != par[0][v]){
		par[0][u] = v;
		h[u] = h[v] + 1;
		paredge[u] = i;
		mn1[u] = mn2[u] = h[u] - 1;
		if(lim1 > i)
			mn1[u] = mn1[v];
		if(lim2 < i)
			mn2[u] = mn2[v];
		dfs(u, i, i);
	}
	return;
}

inline int get(int a, int d){
	d = h[a] - d;
	for(int i = 0; i < lg; i++) if((d >> i) & 1)
		a = par[i][a];
	return a;
}

inline int lca(int a, int b){
	if(h[a] < h[b])
		swap(a, b);
	a = get(a, h[b]);
	if(a == b)
		return a;
	for(int i = lg - 1; i >= 0; i--) if(par[i][a] != par[i][b])
		a = par[i][a], b = par[i][b];
	return par[0][a];
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int n, q; cin >> n >> q;
	for(int i = 0; i < n + q - 1; i++){
		cin >> ty[i] >> a[i] >> b[i];
		a[i]--; b[i]--;
		if(ty[i] == 'S'){
			adj[a[i]].pb({b[i], i});
			adj[b[i]].pb({a[i], i});
		}
		else if(ty[i] != 'Q')
			cout << 1 / 0 << endl;
	}
	
	memset(par, -1, sizeof par);
	dfs(0, n + q + 2, -1);
	
	for(int i = 0; i < n + q - 1; i++) if(ty[i] == 'Q'){
		if(a[i] == b[i]){
			cout << "yes\n";
			continue;
		}
		int c = lca(a[i], b[i]);
		bool re = (mn1[b[i]] <= h[c] && mn2[a[i]] <= h[c]);
		if(c != a[i] && c != b[i]){
			int e1 = paredge[get(b[i], h[c] + 1)];
			int e2 = paredge[get(a[i], h[c] + 1)];
			re &= (e1 < e2);
			re &= (paredge[a[i]] <= i);
		}
		else if(a[i] == c){
			int e = paredge[get(b[i], h[c] + 1)];
			re &= (e <= i);
		}
		else{
			re &= (paredge[a[i]] <= i);
		}
		if(re)
			cout << "yes\n";
		else
			cout << "no\n";
	}
	
	
}

/*
6 3
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
*/

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:65:14: warning: division by zero [-Wdiv-by-zero]
   65 |    cout << 1 / 0 << endl;
      |            ~~^~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 33460 KB Output is correct
2 Correct 80 ms 33696 KB Output is correct
3 Correct 58 ms 33744 KB Output is correct
4 Correct 71 ms 33812 KB Output is correct
5 Correct 64 ms 33848 KB Output is correct
6 Correct 69 ms 33756 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 33460 KB Output is correct
2 Correct 80 ms 33696 KB Output is correct
3 Correct 58 ms 33744 KB Output is correct
4 Correct 71 ms 33812 KB Output is correct
5 Correct 64 ms 33848 KB Output is correct
6 Correct 69 ms 33756 KB Output is correct
7 Runtime error 12 ms 14796 KB Execution killed with signal 4
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 33432 KB Output is correct
2 Correct 155 ms 43880 KB Output is correct
3 Correct 165 ms 43932 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 33432 KB Output is correct
2 Correct 155 ms 43880 KB Output is correct
3 Correct 165 ms 43932 KB Output is correct
4 Runtime error 14 ms 14832 KB Execution killed with signal 4
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 33348 KB Output is correct
2 Correct 128 ms 48184 KB Output is correct
3 Correct 132 ms 48240 KB Output is correct
4 Correct 120 ms 48080 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 33348 KB Output is correct
2 Correct 128 ms 48184 KB Output is correct
3 Correct 132 ms 48240 KB Output is correct
4 Correct 120 ms 48080 KB Output is correct
5 Runtime error 16 ms 14936 KB Execution killed with signal 4
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 33424 KB Output is correct
2 Correct 148 ms 44340 KB Output is correct
3 Correct 155 ms 44864 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 33424 KB Output is correct
2 Correct 148 ms 44340 KB Output is correct
3 Correct 155 ms 44864 KB Output is correct
4 Runtime error 13 ms 14924 KB Execution killed with signal 4
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 33456 KB Output is correct
2 Correct 157 ms 48100 KB Output is correct
3 Correct 148 ms 48204 KB Output is correct
4 Correct 141 ms 48092 KB Output is correct
5 Correct 65 ms 34248 KB Output is correct
6 Correct 151 ms 44360 KB Output is correct
7 Correct 136 ms 44868 KB Output is correct
8 Correct 237 ms 45212 KB Output is correct
9 Correct 178 ms 45248 KB Output is correct
10 Correct 175 ms 48112 KB Output is correct
11 Correct 239 ms 47596 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 33456 KB Output is correct
2 Correct 157 ms 48100 KB Output is correct
3 Correct 148 ms 48204 KB Output is correct
4 Correct 141 ms 48092 KB Output is correct
5 Correct 65 ms 34248 KB Output is correct
6 Correct 151 ms 44360 KB Output is correct
7 Correct 136 ms 44868 KB Output is correct
8 Correct 237 ms 45212 KB Output is correct
9 Correct 178 ms 45248 KB Output is correct
10 Correct 175 ms 48112 KB Output is correct
11 Correct 239 ms 47596 KB Output is correct
12 Runtime error 11 ms 14924 KB Execution killed with signal 4
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 33356 KB Output is correct
2 Correct 66 ms 33676 KB Output is correct
3 Correct 54 ms 33752 KB Output is correct
4 Correct 82 ms 33688 KB Output is correct
5 Correct 55 ms 33876 KB Output is correct
6 Correct 70 ms 33732 KB Output is correct
7 Correct 43 ms 33468 KB Output is correct
8 Correct 165 ms 43960 KB Output is correct
9 Correct 179 ms 43916 KB Output is correct
10 Correct 46 ms 34252 KB Output is correct
11 Correct 123 ms 48224 KB Output is correct
12 Correct 157 ms 48372 KB Output is correct
13 Correct 157 ms 48140 KB Output is correct
14 Correct 45 ms 34328 KB Output is correct
15 Correct 185 ms 44288 KB Output is correct
16 Correct 129 ms 44804 KB Output is correct
17 Correct 250 ms 45296 KB Output is correct
18 Correct 169 ms 45220 KB Output is correct
19 Correct 178 ms 47996 KB Output is correct
20 Correct 281 ms 47696 KB Output is correct
21 Correct 203 ms 44440 KB Output is correct
22 Correct 190 ms 44516 KB Output is correct
23 Correct 205 ms 44680 KB Output is correct
24 Correct 219 ms 44996 KB Output is correct
25 Correct 186 ms 45320 KB Output is correct
26 Correct 140 ms 44280 KB Output is correct
27 Correct 133 ms 44356 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 33356 KB Output is correct
2 Correct 66 ms 33676 KB Output is correct
3 Correct 54 ms 33752 KB Output is correct
4 Correct 82 ms 33688 KB Output is correct
5 Correct 55 ms 33876 KB Output is correct
6 Correct 70 ms 33732 KB Output is correct
7 Correct 43 ms 33468 KB Output is correct
8 Correct 165 ms 43960 KB Output is correct
9 Correct 179 ms 43916 KB Output is correct
10 Correct 46 ms 34252 KB Output is correct
11 Correct 123 ms 48224 KB Output is correct
12 Correct 157 ms 48372 KB Output is correct
13 Correct 157 ms 48140 KB Output is correct
14 Correct 45 ms 34328 KB Output is correct
15 Correct 185 ms 44288 KB Output is correct
16 Correct 129 ms 44804 KB Output is correct
17 Correct 250 ms 45296 KB Output is correct
18 Correct 169 ms 45220 KB Output is correct
19 Correct 178 ms 47996 KB Output is correct
20 Correct 281 ms 47696 KB Output is correct
21 Correct 203 ms 44440 KB Output is correct
22 Correct 190 ms 44516 KB Output is correct
23 Correct 205 ms 44680 KB Output is correct
24 Correct 219 ms 44996 KB Output is correct
25 Correct 186 ms 45320 KB Output is correct
26 Correct 140 ms 44280 KB Output is correct
27 Correct 133 ms 44356 KB Output is correct
28 Runtime error 10 ms 14916 KB Execution killed with signal 4
29 Halted 0 ms 0 KB -