oj.uz

Submission #416071

# Submission time Handle Problem Language Result Execution time Memory
416071 2021-06-01T22:01:47 Z Blagojce Inside information (BOI21_servers) C++11
2.5 / 100
 486 ms 55264 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<ll,ll> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;

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


int n, k;

vector<pii> g[mxn];

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


bool deleted[mxn];

int sub[mxn];

int mark[mxn];

int id;

int locn;


int ti[mxn];
int tout[mxn];


void dfs0(int u, int p){
	ti[u] = tout[u] = -1e9;
	
	
	mark[u] = id;
	
	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]) continue;
		if(sub[e.st] > locn / 2){
			return dfs1(e.st, u);
		}
	}
	return u;
}


int ccen;


void dfs2(int u, int p, int w, int wmin){
	ti[u] = wmin;
	tout[u] = w;
	for(auto e : g[u]){
		if(e.st == p || deleted[e.st]) continue;
		
		if(e.nd > w){
			dfs2(e.st, u, e.nd, wmin);
		}
	}
}
string ans[mxn];


void dfs3(int u, int p, int w, int wmax){
	for(auto e : Q[u]){
		if(e.st == ccen){
			if(e.nd > wmax){
				ans[e.nd] = "yes";
			}
		}
		else{
			if(mark[u] != mark[e.st]) continue;
			
			if(e.nd > tout[e.st] && ti[e.st] > wmax){
				ans[e.nd] = "yes";
			}
		}
	}
	
	for(auto e : g[u]){
		if(e.st == p || deleted[e.st]) continue;
		
		if(e.nd < w){
			dfs3(e.st, u, e.nd, wmax);
		}
	}
}


void decompose(int u, int p){
	++id;
	dfs0(u, u);
	
	locn = sub[u];
	int cen = dfs1(u, u);
	ccen = cen;
	
	for(auto e : g[cen]){
		if(deleted[e.st]) continue;
		dfs2(e.st, cen, e.nd, e.nd);
	}
	
	for(auto e : g[cen]){
		if(deleted[e.st]) continue;
		dfs3(e.st, cen, e.nd, e.nd);
	}
	
	for(auto e : Q[u]){
		
		if(mark[e.st] != mark[cen]) continue;
		if(e.st == cen){
			ans[e.nd] = "yes";
		}
		else{
			if(tout[e.st] < e.nd){
				ans[e.nd] = "yes";
			}
		}
	}
	
	
	deleted[cen] = true;
	for(auto e : g[cen]){
		if(deleted[e.st]) continue;
		decompose(e.st, cen);
	}
}


bool qry[mxn];

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	
}

Subtask #1
0 / 2.5

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

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 261 ms 45488 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 282 ms 45504 KB Output is correct
2 Correct 486 ms 55264 KB Output is correct
3 Correct 429 ms 55240 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 282 ms 45504 KB Output is correct
2 Correct 486 ms 55264 KB Output is correct
3 Correct 429 ms 55240 KB Output is correct
4 Incorrect 273 ms 45152 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 268 ms 45396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

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

Subtask #12
0 / 17.5

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