Submission #245677

#	Time	Username	Problem	Language	Result	Execution time	Memory
245677		dennisstar	Izlet (COI19_izlet)	C++17	100 / 100	935 ms	82072 KiB

izlet

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
using pii = pair<int, int>;

const int MX = 3e3 + 5;

int pr[MX];
int gp(int n) { return pr[n]?(pr[n]=gp(pr[n])):n; }
void un(int x, int y) {
	x=gp(x), y=gp(y);
	if (x!=y) pr[y]=x;
}

int T, N, mt[MX][MX], clr[MX], dst[MX][MX];
vector<int> stk;
vector<pii> a;

void dfs(int n, int p) {
	if (p) {
		pii mn(MX, 0);
		for (auto &i:stk) if (mt[i][n]==mt[i][p]) mn=min(mn, pii(dst[i][n], clr[i]));
		if (mn.second) clr[n]=mn.second;
		else clr[n]=++T;
	}else clr[n]=++T;

	stk.eb(n);
	for (int i=1; i<=N; i++) if (!clr[i]&&gp(i)==i&&mt[i][n]==2) {
		for (auto &j:stk) dst[i][j]=dst[j][i]=dst[n][j]+1;
		a.eb(n, i);
		dfs(i, n);
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>T>>N;
	for (int i=1; i<=N; i++) for (int j=1; j<=N; j++) {
		cin>>mt[i][j];
		if (mt[i][j]==1) un(i, j);
	}

	dfs(gp(1), T=0);

	for (int i=1; i<=N; i++) cout<<clr[gp(i)]<<' ';
	cout<<'\n';
	for (auto &i:a) cout<<i.first<<' '<<i.second<<'\n';
	for (int i=1; i<=N; i++) if (gp(i)!=i) cout<<gp(i)<<' '<<i<<'\n';
	return 0;
}

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