oj.uz

Submission #393756

# Submission time Handle Problem Language Result Execution time Memory
393756 2021-04-24T12:45:17 Z ronnith Izlet (COI19_izlet) C++14
18 / 100
 604 ms 53212 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 597 ms 53144 KB Output is correct
3 Correct 598 ms 53208 KB Output is correct
4 Correct 596 ms 53212 KB Output is correct
5 Correct 604 ms 53060 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 597 ms 53144 KB Output is correct
3 Correct 598 ms 53208 KB Output is correct
4 Correct 596 ms 53212 KB Output is correct
5 Correct 604 ms 53060 KB Output is correct
6 Incorrect 1 ms 204 KB Unexpected end of file - int32 expected
7 Halted 0 ms 0 KB -