oj.uz

Submission #416541

# Submission time Handle Problem Language Result Execution time Memory
416541 2021-06-02T15:09:50 Z Blagojce Inside information (BOI21_servers) C++11
2.5 / 100
 413 ms 25852 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;

mt19937 _rand(time(NULL));
const int mxn = 2e5;


int n, k;


vector<pii> g[mxn];
void add_edge(int a, int b, int w){
	g[a].pb({b, w});
	g[b].pb({a, w});
}

vector<pii> Q[mxn];
vector<int> C[mxn];

int qry[2*mxn];


bool deleted[mxn];
int sub[mxn];

int cn;




int tin[mxn];


void dfs0(int u, int p){
	sub[u] = 1;
	for(auto e : g[u]){
		if(e.st == p || deleted[e.st]) continue;
		dfs0(e.st, u);
		sub[u] += sub[e.st];
	}
}
int dfs1(int u, int p){
	for(auto e : g[u]){
		if(e.st != p && !deleted[e.st] && sub[e.st] > cn/2){
			return dfs1(e.st, u);
		}
	}
	return u;
}

int ans[2*mxn];


int ccen;


void inc(int u, int p, int cw){
	tin[u] = cw;	
	
	for(auto e : g[u]){
		if(e.st != p && !deleted[e.st] && e.nd >= cw){
			inc(e.st, u, e.nd);
		}
	}
}
int active_w;

void dec(int u, int p, int cw){
	for(auto q : Q[u]){
		if(q.st == ccen){
			if(active_w <= q.nd){
				ans[q.nd] = 1;
			}
			
			continue;
		}
		
		if(tin[q.st] <= q.nd){
			ans[q.nd] = 1;
		}
	}
	for(auto e : g[u]){
		if(e.st != p && !deleted[e.st] && e.nd <= cw){
			dec(e.st, u, e.nd);
		}
	}
}


void clr(int u, int p){
	tin[u] = 1e9;
	for(auto e : g[u]){
		if(e.st == p || deleted[e.st]) continue;
		clr(e.st, u);
	}
}

void decompose(int u, int p){
	dfs0(u, u);
	cn = sub[u];
	
	int cen = dfs1(u, u);
	ccen = cen;
	
	sort(all(g[cen]), [](const pii &v1, const pii &v2){
		return v1.nd > v2.nd;
	});
	
	
	for(auto e : g[u]){
		if(deleted[e.st]) continue;
		active_w = e.nd;
		dec(e.st, cen, e.nd);
		inc(e.st, cen, e.nd);
	}
	for(auto q : Q[u]){
		if(tin[q.st] <= q.nd){
			ans[q.nd] = 1;
		}
	}
	clr(cen, cen);
	
	deleted[cen] = true;
	for(auto e : g[u]){
		if(deleted[e.st]) continue;
		decompose(e.st, cen);
	}
}



void solve(){
	cin >> n >> k;
	fr(i, 0, n+k-1){
		char t;
		cin >> t;
		if(t == 'S'){
			qry[i] = 0;
			int u, v;
			cin >> u >> v;
			--u, --v;
			add_edge(u, v, i);
		}
		else if(t == 'Q'){
			qry[i] = 1;
			int u, v;
			cin >> u >> v;
			--u, --v;
			if(u == v){
				ans[i] = 1;
			}
			else Q[v].pb({u, i});
		}
		else{
			qry[i] = 2;
			int u;
			cin >> u;
			--u;
			C[u].pb(i);
		}
	}
	clr(0, 0);
	decompose(0, -1);
	fr(i, 0, n+k-1){
		if(qry[i] == 0) continue;
		if(qry[i] == 1){
			if(ans[i] == 1) cout<<"yes"<<endl;
			else cout<<"no"<<endl;
		}
		else{
			//cout<<1<<endl;
		}
	}
}

int main(){
	//freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	
}
/*
7 2
S 1 2
S 2 4
S 5 2
S 3 7
S 1 3
S 3 6
Q 6 7
Q 7 6
*/

Subtask #1
0 / 2.5

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

Subtask #2
0 / 2.5

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

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 214 ms 18204 KB Output is correct
2 Correct 398 ms 25852 KB Output is correct
3 Correct 413 ms 25820 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 214 ms 18204 KB Output is correct
2 Correct 398 ms 25852 KB Output is correct
3 Correct 413 ms 25820 KB Output is correct
4 Incorrect 207 ms 18172 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

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

Subtask #12
0 / 17.5

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