Submission #969575

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
969575	2024-04-25T10:16:16 Z	NotLinux	Inside information (BOI21_servers)	C++17	5 / 100	3500 ms	11160 KB

servers

//author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
const int N = 120005;
const int inf = 1e9 + 7;
int vis[N] , ttime = 1;
vector < pair < int , int > > graph[N];
void dfs1(int node , int mn){
	if(vis[node])return;
	// cout << "dfs1 : " << node << " , " << mn << endl;
	// cout << "graph : ";for(auto itr : graph[node])cout << itr.first << "," << itr.second << "   ";cout << endl;
	vis[node] = 1;
	for(auto itr : graph[node]){
		if(itr.second > mn){
			dfs1(itr.first , itr.second);
		}
	}
}
void solve(){
	int n,k;
	cin >> n >> k;
	int q_no = n + k - 1;
	while(q_no--){
		char ch;
		cin >> ch;
		if(ch == 'S'){
			int a,b;
			cin >> a >> b;
			graph[a].push_back({b , ttime});
			graph[b].push_back({a , ttime});
			ttime++;
		}
		else if(ch == 'Q'){
			int a,d;
			cin >> a >> d;
			fill(vis , vis + n + 1 , 0);
			dfs1(d , -inf);
			cout << (vis[a] ? "yes" : "no") << '\n';
		}
		else{
			int d;
			cin >> d;
			fill(vis , vis + n + 1 , 0);
			dfs1(d , -inf);
			cout << count(vis , vis + n + 1 , 1) << '\n';
		}
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

Subtask #1
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	4440 KB	Output is correct
2	Correct	47 ms	4948 KB	Output is correct
3	Correct	88 ms	5044 KB	Output is correct
4	Correct	44 ms	5028 KB	Output is correct
5	Correct	44 ms	4948 KB	Output is correct
6	Correct	875 ms	5228 KB	Output is correct

Subtask #2
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	4440 KB	Output is correct
2	Correct	47 ms	4948 KB	Output is correct
3	Correct	88 ms	5044 KB	Output is correct
4	Correct	44 ms	5028 KB	Output is correct
5	Correct	44 ms	4948 KB	Output is correct
6	Correct	875 ms	5228 KB	Output is correct
7	Correct	22 ms	4444 KB	Output is correct
8	Correct	193 ms	4692 KB	Output is correct
9	Correct	305 ms	5200 KB	Output is correct
10	Correct	190 ms	4692 KB	Output is correct
11	Correct	191 ms	4732 KB	Output is correct
12	Correct	1065 ms	5260 KB	Output is correct

Subtask #3
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	4444 KB	Output is correct
2	Execution timed out	3557 ms	6908 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	4444 KB	Output is correct
2	Execution timed out	3557 ms	6908 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	4428 KB	Output is correct
2	Correct	777 ms	11096 KB	Output is correct
3	Correct	797 ms	11092 KB	Output is correct
4	Execution timed out	3533 ms	8628 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	4428 KB	Output is correct
2	Correct	777 ms	11096 KB	Output is correct
3	Correct	797 ms	11092 KB	Output is correct
4	Execution timed out	3533 ms	8628 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	4436 KB	Output is correct
2	Execution timed out	3552 ms	11116 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	4436 KB	Output is correct
2	Execution timed out	3552 ms	11116 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #9
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	4440 KB	Output is correct
2	Correct	817 ms	11160 KB	Output is correct
3	Correct	841 ms	11092 KB	Output is correct
4	Execution timed out	3524 ms	8784 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	4440 KB	Output is correct
2	Correct	817 ms	11160 KB	Output is correct
3	Correct	841 ms	11092 KB	Output is correct
4	Execution timed out	3524 ms	8784 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #11
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	4424 KB	Output is correct
2	Correct	46 ms	4948 KB	Output is correct
3	Correct	90 ms	5044 KB	Output is correct
4	Correct	47 ms	5716 KB	Output is correct
5	Correct	44 ms	4944 KB	Output is correct
6	Correct	848 ms	5044 KB	Output is correct
7	Correct	24 ms	4440 KB	Output is correct
8	Execution timed out	3564 ms	7012 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	4424 KB	Output is correct
2	Correct	46 ms	4948 KB	Output is correct
3	Correct	90 ms	5044 KB	Output is correct
4	Correct	47 ms	5716 KB	Output is correct
5	Correct	44 ms	4944 KB	Output is correct
6	Correct	848 ms	5044 KB	Output is correct
7	Correct	24 ms	4440 KB	Output is correct
8	Execution timed out	3564 ms	7012 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Submission #969575

Compilation message