Submission #464040

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
464040	2021-08-12T09:52:08 Z	prvocislo	Party (POI11_imp)	C++17	90 / 100	1828 ms	65540 KB

#include <iostream>
#include <vector>
#include <set>
using namespace std;

const int maxn = 3005;
int n, m;
vector<vector<bool> > g(maxn, vector<bool>(maxn, false));
set<pair<int, int> > s;
void rmv(int i)
{
	for (int j = 0; j < n; j++) if (!g[i][j])
	{
		if (s.count({ i,j })) s.erase({ i, j });
		if (s.count({ j,i })) s.erase({ j, i });
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0, a, b; i < m; i++)
	{
		cin >> a >> b;
		a--, b--;
		g[a][b] = g[b][a] = true;
	}
	for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) if (!g[i][j]) s.insert({ i,j });
	vector<bool> alive(n, true);
	while (!s.empty())
	{
		int a = s.begin()->first, b = s.begin()->second;
		rmv(a), rmv(b);
		alive[a] = false, alive[b] = false;
	}
	vector<int> k;
	for (int i = 0; i < n; i++) if (alive[i]) k.push_back(i);
	for (int i = 0; i < n / 3; i++) cout << k[i] + 1 << " \n"[i == n / 3 - 1];
	return 0;
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1484 KB	Output is correct
2	Correct	3 ms	1484 KB	Output is correct
3	Correct	4 ms	1612 KB	Output is correct
4	Correct	4 ms	1624 KB	Output is correct
5	Correct	4 ms	1612 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	1868 KB	Output is correct
2	Correct	36 ms	3580 KB	Output is correct
3	Correct	33 ms	3524 KB	Output is correct
4	Correct	35 ms	3468 KB	Output is correct
5	Correct	36 ms	3528 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	3116 KB	Output is correct
2	Correct	147 ms	9860 KB	Output is correct
3	Correct	132 ms	9600 KB	Output is correct
4	Correct	151 ms	9668 KB	Output is correct
5	Correct	150 ms	9772 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	5060 KB	Output is correct
2	Correct	376 ms	20864 KB	Output is correct
3	Correct	335 ms	20612 KB	Output is correct
4	Correct	369 ms	20696 KB	Output is correct
5	Correct	383 ms	20600 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	140 ms	9604 KB	Output is correct
2	Correct	556 ms	29436 KB	Output is correct
3	Correct	505 ms	29216 KB	Output is correct
4	Correct	575 ms	29380 KB	Output is correct
5	Correct	586 ms	29304 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	466 ms	24260 KB	Output is correct
2	Correct	699 ms	36292 KB	Output is correct
3	Correct	643 ms	35984 KB	Output is correct
4	Correct	710 ms	36044 KB	Output is correct
5	Correct	731 ms	36032 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	889 ms	42584 KB	Output is correct
2	Correct	946 ms	47624 KB	Output is correct
3	Correct	860 ms	47184 KB	Output is correct
4	Correct	1000 ms	47468 KB	Output is correct
5	Correct	996 ms	47284 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1239 ms	56608 KB	Output is correct
2	Correct	1179 ms	56376 KB	Output is correct
3	Correct	1048 ms	55768 KB	Output is correct
4	Correct	1279 ms	56072 KB	Output is correct
5	Correct	1197 ms	56128 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1656 ms	65536 KB	Output is correct
2	Correct	1426 ms	65484 KB	Output is correct
3	Correct	1280 ms	65148 KB	Output is correct
4	Correct	1372 ms	65140 KB	Output is correct
5	Correct	1413 ms	65512 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1828 ms	65536 KB	Output is correct
2	Correct	1643 ms	65536 KB	Output is correct
3	Correct	1486 ms	65536 KB	Output is correct
4	Correct	1760 ms	65536 KB	Output is correct
5	Correct	1828 ms	65536 KB	Output is correct

Subtask #11
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1022 ms	65540 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Submission #464040

Compilation message