답안 #245677

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245677 2020-07-07T06:21:19 Z dennisstar Izlet (COI19_izlet) C++17
100 / 100
935 ms 82072 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 713 ms 71988 KB Output is correct
3 Correct 693 ms 72056 KB Output is correct
4 Correct 573 ms 52472 KB Output is correct
5 Correct 608 ms 64504 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 634 ms 66412 KB Output is correct
2 Correct 554 ms 57476 KB Output is correct
3 Correct 808 ms 72092 KB Output is correct
4 Correct 815 ms 71692 KB Output is correct
5 Correct 553 ms 48132 KB Output is correct
6 Correct 631 ms 54684 KB Output is correct
7 Correct 443 ms 46584 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 713 ms 71988 KB Output is correct
3 Correct 693 ms 72056 KB Output is correct
4 Correct 573 ms 52472 KB Output is correct
5 Correct 608 ms 64504 KB Output is correct
6 Correct 634 ms 66412 KB Output is correct
7 Correct 554 ms 57476 KB Output is correct
8 Correct 808 ms 72092 KB Output is correct
9 Correct 815 ms 71692 KB Output is correct
10 Correct 553 ms 48132 KB Output is correct
11 Correct 631 ms 54684 KB Output is correct
12 Correct 443 ms 46584 KB Output is correct
13 Correct 821 ms 69500 KB Output is correct
14 Correct 935 ms 73872 KB Output is correct
15 Correct 576 ms 60728 KB Output is correct
16 Correct 577 ms 48248 KB Output is correct
17 Correct 617 ms 50168 KB Output is correct
18 Correct 846 ms 82072 KB Output is correct
19 Correct 724 ms 75172 KB Output is correct
20 Correct 625 ms 68728 KB Output is correct
21 Correct 660 ms 64376 KB Output is correct
22 Correct 712 ms 72056 KB Output is correct
23 Correct 690 ms 62456 KB Output is correct
24 Correct 712 ms 59512 KB Output is correct
25 Correct 574 ms 61944 KB Output is correct