Submission #896971

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
896971	2024-01-02T11:38:39 Z	vjudge1	Game (APIO22_game)	C++17	30 / 100	4000 ms	2936 KB

game

#include<bits/stdc++.h>
using namespace std;
#include "game.h"


int k1,n1;

vector<vector<int>> G,Grev, DAG;
vector<int> top,used,scc;
int act = 0;
void dfs(int u){
	if(used[u]) return;
	used[u] = 1;
	// cerr<<"START "<<u<<endl;
	for(int v : G[u]) dfs(v);
	// cerr<<"END "<<u<<endl;
	top.push_back(u);
}

void dfs1(int u){
	if(used[u]) return;
	used[u] = 1;
	for(int v : Grev[u]){
		dfs1(v);
	}
	scc[u] = act;
}

void init(int n, int k) {
	k1 = k; n1 = n;
	G.assign(n,vector<int>());
	Grev = G;
	// cerr<<"HERE "<<n<<" "<<k<<endl;
	for(int i = 0; i<=k-2; i++){
		G[i].push_back(i+1);
		Grev[i+1].push_back(i);
	}
}

int add_teleporter(int u, int v) {
	if(u == v){
		if(u < k1) return 1;
		return 0;
	}
	G[u].push_back(v);
	Grev[v].push_back(u);
	used.assign(n1,0);
	scc.assign(n1,-1);
	top.clear();
	// cerr<<"STARTING DFS OF EDGE "<<u<<" "<<v<<endl;

	for(int i = 0; i<n1; i++) dfs(i);
	// cerr<<"TOP"<<endl;
	// for(int i : top) cerr<<i<<" ";
		// cerr<<"END TOP"<<endl;
	used.assign(n1,0);
	act = 0;
	for(int i = top.size()-1; i>=0; i--){
		if(!used[top[i]]) act++, scc[top[i]] = act, dfs1(top[i]);
	}
	set<int> hv; 
	for(int i = 0; i<k1; i++){
		hv.insert(scc[i]);
	}
	//  cerr<<"STARTING SCC OF EDGE: "<<u<<" "<<v<<endl;
	// for(int i = 0; i<n1; i++){
	// 	cerr<<"SCC: "<<i<<" "<<scc[i]<<endl;
	// }
	// cerr<<endl;
	if(hv.size() < k1) return 1;

	for(int i = k1; i<n1; i++){
		if(hv.count(scc[i])) return 1;
	}
  return 0;
}

Compilation message

game.cpp: In function 'int add_teleporter(int, int)':
game.cpp:70:15: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |  if(hv.size() < k1) return 1;
      |     ~~~~~~~~~~^~~~

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	2 ms	344 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	2 ms	592 KB	Output is correct
6	Correct	2 ms	344 KB	Output is correct
7	Correct	2 ms	344 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	2 ms	344 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	2 ms	592 KB	Output is correct
6	Correct	2 ms	344 KB	Output is correct
7	Correct	2 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	1 ms	344 KB	Output is correct
19	Correct	1 ms	344 KB	Output is correct

Subtask #3
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	2 ms	344 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	2 ms	592 KB	Output is correct
6	Correct	2 ms	344 KB	Output is correct
7	Correct	2 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	1 ms	344 KB	Output is correct
19	Correct	1 ms	344 KB	Output is correct
20	Correct	19 ms	612 KB	Output is correct
21	Correct	3 ms	344 KB	Output is correct
22	Correct	20 ms	516 KB	Output is correct
23	Correct	19 ms	508 KB	Output is correct
24	Correct	46 ms	576 KB	Output is correct
25	Correct	195 ms	552 KB	Output is correct
26	Correct	208 ms	856 KB	Output is correct
27	Correct	238 ms	580 KB	Output is correct
28	Correct	109 ms	576 KB	Output is correct
29	Correct	221 ms	1072 KB	Output is correct

Subtask #4
0.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	2 ms	344 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	2 ms	592 KB	Output is correct
6	Correct	2 ms	344 KB	Output is correct
7	Correct	2 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	1 ms	344 KB	Output is correct
19	Correct	1 ms	344 KB	Output is correct
20	Correct	19 ms	612 KB	Output is correct
21	Correct	3 ms	344 KB	Output is correct
22	Correct	20 ms	516 KB	Output is correct
23	Correct	19 ms	508 KB	Output is correct
24	Correct	46 ms	576 KB	Output is correct
25	Correct	195 ms	552 KB	Output is correct
26	Correct	208 ms	856 KB	Output is correct
27	Correct	238 ms	580 KB	Output is correct
28	Correct	109 ms	576 KB	Output is correct
29	Correct	221 ms	1072 KB	Output is correct
30	Execution timed out	4032 ms	2936 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	2 ms	344 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	2 ms	592 KB	Output is correct
6	Correct	2 ms	344 KB	Output is correct
7	Correct	2 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	1 ms	344 KB	Output is correct
19	Correct	1 ms	344 KB	Output is correct
20	Correct	19 ms	612 KB	Output is correct
21	Correct	3 ms	344 KB	Output is correct
22	Correct	20 ms	516 KB	Output is correct
23	Correct	19 ms	508 KB	Output is correct
24	Correct	46 ms	576 KB	Output is correct
25	Correct	195 ms	552 KB	Output is correct
26	Correct	208 ms	856 KB	Output is correct
27	Correct	238 ms	580 KB	Output is correct
28	Correct	109 ms	576 KB	Output is correct
29	Correct	221 ms	1072 KB	Output is correct
30	Execution timed out	4032 ms	2936 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Submission #896971

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 10.0 / 10.0

Subtask #3 18.0 / 18.0

Subtask #4 0.0 / 30.0

Subtask #5 0.0 / 40.0

Subtask #1
2.0 / 2.0

Subtask #2
10.0 / 10.0

Subtask #3
18.0 / 18.0

Subtask #4
0.0 / 30.0

Subtask #5
0.0 / 40.0