Submission #488746

#	Time	Username	Problem	Language	Result	Execution time	Memory
488746		CSQ31	Inside information (BOI21_servers)	C++17	2.50 / 100	3564 ms	14924 KiB

servers

#include<bits/stdc++.h>
using namespace std;
//sub 1/2 trivial
//sub 3 path of smaller or larger edges
//sub task 4 binary tree can directly traverse the tree since logn height
//sub 5
//sub 6
#define pb push_back
#define fi first
#define se second
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int,int> pii;
const int MAXN = 3e5;
vector<pii>adj[MAXN];
int cnt = 0,ans = 0;
bool dfs(int v,int u,int tar,int last){
	if(v==tar)return 1;
	bool ok = 0;
	for(pii x:adj[v]){
		if(x.fi==u)continue;
		if(x.se < last)ok = ok|dfs(x.fi,v,tar,x.se);
	}
	return ok;
}
void dfs(int v,int u,int last){
	ans++;
	for(pii x:adj[v]){
		if(x.fi==u)continue;
		if(x.se > last)dfs(x.fi,u,x.se);
	}
	
}
int main()
{
	owo
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n+k-1;i++){
		char c;
		cin>>c;
		if(c=='S'){
			int v,u;
			cin>>v>>u;
			adj[v].pb({u,++cnt});
			adj[u].pb({v,cnt});
		}
		if(c=='Q'){
			int a,d;
			cin>>a>>d;
			if(dfs(a,0,d,1e9))cout<<"yes"<<'\n';
			else cout<<"no"<<'\n';
		}
		if(c=='C'){
			int d;cin>>d;
			cout<<1<<'\n';
		}
		
	}
	
	
	
}

• Subtask 1: 2.5 / 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