Submission #668433

#	Time	Username	Problem	Language	Result	Execution time	Memory
668433		mychecksedad	Inside information (BOI21_servers)	C++17	0 / 100	106 ms	89676 KiB

servers

#include <bits/stdc++.h>
using namespace std;
const int N = 120002;
#define pb push_back

int n, q;
deque<pair<int, int>> g[N];
vector<pair<int, int>> Dfs, queries[N];
vector<array<int, 3>> Q[N];
vector<bool> ans;
void dfs(int v, int cur){
	for(auto qq: queries[v]) if(qq.second >= cur) ans[qq.first] = 1;

	for(auto qq: Q[v]) queries[qq[0]].pb({qq[1], qq[2]});

	while(!g[v].empty()){
		int u = g[v].front().first, e = g[v].front().second;
		if(e > cur){
			dfs(u, e);
		}
		g[v].pop_front();
	}		

	for(auto qq: Q[v]) queries[qq[0]].pop_back();
}

void solve(){
	cin >> n >> q;
	int c = 0;
	ans.resize(q);
	for(int i = 0; i < q + n - 1; ++i){
		char s; 
		cin >> s;
		if(s == 'S'){
			int u, v; cin >> u >> v;
			g[u].pb({v, i});
			g[v].pb({u, i});
			Dfs.pb({v, i});
			Dfs.pb({u, i});
		}else if(s == 'Q'){
			int u, d; cin >> u >> d;
			Q[d].pb({u, c++, i});
		}else{
			int d; cin >> d; c++;
		}
	}
	for(auto e: Dfs){
		dfs(e.first, e.second - 1);
	}
	for(int a: ans){
		cout << (a ? "yes" : "no") << '\n';
	}
}


int main(){
	solve();
	return 0;
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5