제출 #464040

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
464040		prvocislo	Untitled (POI11_imp)	C++17	90 / 100	1828 ms	65540 KiB

Main

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 0 / 10