oj.uz

Submission #157789

# Submission time Handle Problem Language Result Execution time Memory
157789 2019-10-13T00:36:27 Z imyujin Izlet (COI19_izlet) C++17
18 / 100
 656 ms 53660 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[x] == 1) k++;
	//printf("k = %d\n", k);
	if(A[v][x] < k) {
		cnt[x]--;
		return ans[x];
	}
	for(auto a : ed[x]) if(a != p) {
		int t = dfs(v, a, x, k);
		if(t) {
			cnt[x]--;
			return t;
		}
	}
	cnt[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 504 KB Output is correct
2 Correct 656 ms 53660 KB Output is correct
3 Correct 642 ms 53584 KB Output is correct
4 Correct 647 ms 53408 KB Output is correct
5 Correct 648 ms 53336 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 637 ms 53592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 656 ms 53660 KB Output is correct
3 Correct 642 ms 53584 KB Output is correct
4 Correct 647 ms 53408 KB Output is correct
5 Correct 648 ms 53336 KB Output is correct
6 Incorrect 637 ms 53592 KB Output isn't correct
7 Halted 0 ms 0 KB -