Submission #393756

#	Time	Username	Problem	Language	Result	Execution time	Memory
393756		ronnith	Izlet (COI19_izlet)	C++14	18 / 100	604 ms	53212 KiB

izlet

#include <bits/stdc++.h>

using namespace std;

const int N = (int)3e3;
int n, color[N];
int d[N][N];
bool vis[N];
vector<pair<int, int>> edges;

void dfs(int x, int cr) {
	vis[x] = true;
	color[x] = cr;
	for(int i = 0;i < n;i ++) {
		if(d[x][i] == 1 && !vis[i]) {
			edges.emplace_back(x, i);
			dfs(i, cr);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int sub;
	cin >> sub;
	if(sub == 1) {
		cin >> n;
		for(int i = 0;i < n;i ++) {
			for(int j = 0;j < n;j ++) {
				cin >> d[i][j];
			}
		}
		int prev = -1;
		int cnt = 0;
		for(int i = 0;i < n;i ++) {
			if(!vis[i]) {
				dfs(i, cnt % 2);
				if(prev != -1) {
//					cerr << prev+1 << ' ' << i+1 << '\n';
					edges.emplace_back(prev, i);
				}
				prev = i;
				cnt ++;
			}
		}
		for(int i = 0;i < n;i ++) {
			cout << color[i]+1 << ' ';
		}
		cout << '\n';
		for(auto e : edges) {
			cout << e.first+1 << ' ' << e.second+1 << '\n';
		}
	}
	return 0;
}

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