oj.uz

Submission #523444

# Submission time Handle Problem Language Result Execution time Memory
523444 2022-02-07T16:19:29 Z fatemetmhr Inside information (BOI21_servers) C++17
0 / 100
 92 ms 33456 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);
		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
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 33348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 33348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 33384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 33384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 33452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 33452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 33456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 33456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 33340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 33340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 33436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 33436 KB Output isn't correct
2 Halted 0 ms 0 KB -