oj.uz

Submission #157790

# Submission time Handle Problem Language Result Execution time Memory
157790 2019-10-13T00:43:25 Z imyujin Izlet (COI19_izlet) C++17
100 / 100
 931 ms 74812 KB 
#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) {
	//printf("dfs(v = %d, x = %d, p = %d, k = %d)\n", v, x, p, k);
	if(++cnt[ans[x]] == 1) k++;
	//printf("k = %d\n", 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;
			//printf("x = %d, i = %d, ans = %d\n", x, i, ans[i]);
			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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 639 ms 36820 KB Output is correct
3 Correct 635 ms 36644 KB Output is correct
4 Correct 634 ms 36632 KB Output is correct
5 Correct 640 ms 36588 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 36644 KB Output is correct
2 Correct 645 ms 53480 KB Output is correct
3 Correct 891 ms 74012 KB Output is correct
4 Correct 931 ms 74812 KB Output is correct
5 Correct 629 ms 53540 KB Output is correct
6 Correct 740 ms 60552 KB Output is correct
7 Correct 514 ms 49368 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 639 ms 36820 KB Output is correct
3 Correct 635 ms 36644 KB Output is correct
4 Correct 634 ms 36632 KB Output is correct
5 Correct 640 ms 36588 KB Output is correct
6 Correct 634 ms 36644 KB Output is correct
7 Correct 645 ms 53480 KB Output is correct
8 Correct 891 ms 74012 KB Output is correct
9 Correct 931 ms 74812 KB Output is correct
10 Correct 629 ms 53540 KB Output is correct
11 Correct 740 ms 60552 KB Output is correct
12 Correct 514 ms 49368 KB Output is correct
13 Correct 661 ms 54384 KB Output is correct
14 Correct 811 ms 61484 KB Output is correct
15 Correct 629 ms 53688 KB Output is correct
16 Correct 739 ms 58024 KB Output is correct
17 Correct 746 ms 59940 KB Output is correct
18 Correct 656 ms 53576 KB Output is correct
19 Correct 665 ms 53556 KB Output is correct
20 Correct 633 ms 53540 KB Output is correct
21 Correct 651 ms 54520 KB Output is correct
22 Correct 682 ms 53788 KB Output is correct
23 Correct 660 ms 54280 KB Output is correct
24 Correct 742 ms 60536 KB Output is correct
25 Correct 635 ms 53524 KB Output is correct