Submission #157791

#	Time	Username	Problem	Language	Result	Execution time	Memory
157791		imyujin	Izlet (COI19_izlet)	C++17	100 / 100	907 ms	40008 KiB

izlet

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

typedef pair<int, int> pii;

const int MAXN = 3010;

int A[MAXN][MAXN];
bool chk[MAXN];
int cnt[MAXN];
int ans[MAXN], cn;
vector<int> ed[MAXN];
int uni[MAXN];
vector<pii> edges;

int guni(int x) { return uni[x] ? uni[x] = guni(uni[x]) : x; }
void unite(int x, int y) { uni[guni(y)] = guni(x); }

int dfs(int v, int x, int p, int k) {
	if(++cnt[ans[x]] == 1) k++;
	if(A[v][x] < k) {
		cnt[ans[x]]--;
		return ans[x];
	}
	for(auto a : ed[x]) if(a != p) {
		int t = dfs(v, a, x, k);
		if(t) {
			cnt[ans[x]]--;
			return t;
		}
	}
	cnt[ans[x]]--;
	return 0;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N;

	cin >> N;
	cin >> N;
	for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) cin >> A[i][j];

	for(int i = 1; i <= N; i++) for(int j = i + 1; j <= N; j++) if(A[i][j] == 1 && guni(i) != guni(j)) {
		edges.emplace_back(i, j);
		unite(i, j);
	}

	vector<int> v = {1};
	ans[1] = cn = 1;
	chk[1] = true;
	while(!v.empty()) {
		int x = v.back();
		v.pop_back();
		for(int i = 1; i <= N; i++) if(A[x][i] == 2 && !chk[i] && guni(i) == i) {
			ans[i] = dfs(i, x, 0, 1);
			if(!ans[i]) ans[i] = ++cn;
			ed[x].push_back(i);
			ed[i].push_back(x);
			edges.emplace_back(x, i);
			chk[i] = true;
			v.push_back(i);
		}
	}

	for(int i = 1; i <= N; i++) cout << ans[guni(i)] << " ";
	cout << "\n";
	for(auto a : edges) cout << a.first << " " << a.second << "\n";
	return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57