oj.uz

답안 #418356

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
418356 2021-06-05T10:13:54 Z Josia Split the Attractions (IOI19_split) C++14
18 / 100
 126 ms 13856 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;


int numberVisited = 0;
void DFS(vector<int> &result, vector<bool> &visited, vector<vector<int>> &graph, int v, int b) {
	if (visited[v] || numberVisited == b) {
		return;
	}
	visited[v] = 1;
	result[v] = 2;
	numberVisited ++;

	for (int i: graph[v]) {
		if (visited[i]) continue;
		DFS(result, visited, graph, i, b);
	}
}





vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> res(n, 0);
	

	vector<int> numEdges(n, 0);


	vector<vector<int>> graph(n);

	for (int i = 0; i<p.size(); i++) {
		numEdges[p[i]]++;
		numEdges[q[i]]++;
		graph[p[i]].push_back(q[i]);
		graph[q[i]].push_back(p[i]);
	}

	bool cycle = 1;
	bool path = 1;
	for (int i: numEdges) {
		if (i != 2) cycle = 0;
		if (i > 2) path = 0;
	}

	if (cycle) path = 0;

	if (cycle) {
		vector<bool> visited(n, 0);
		int v = 0;
		for (int i = 0; i<a; i++) {
			assert(!visited[v]);
			visited[v] = 1;
			res[v] = 1;
			for (int i: graph[v]) {
				if (visited[i]) continue;
				else {v = i; break;}
			}
		}
		for (int i = 0; i<b; i++) {
			assert(!visited[v]);
			visited[v] = 1;
			res[v] = 2;
			for (int i: graph[v]) {
				if (visited[i]) continue;
				else {v = i; break;}
			}
		}
		for (int i = 0; i<c; i++) {
			assert(!visited[v]);
			visited[v] = 1;
			res[v] = 3;
			for (int i: graph[v]) {
				if (visited[i]) continue;
				else {v = i; break;}
			}
		}
	}


	if (path) {
		vector<bool> visited(n, 0);
		int v = 0;

		for (int i = 0; i<n; i++) {
			if (numEdges[i] == 1) {v = i; break;}
		}

		for (int i = 0; i<a; i++) {
			assert(!visited[v]);
			visited[v] = 1;
			res[v] = 1;
			for (int i: graph[v]) {
				if (visited[i]) continue;
				else {v = i; break;}
			}
		}
		for (int i = 0; i<b; i++) {
			assert(!visited[v]);
			visited[v] = 1;
			res[v] = 2;
			for (int i: graph[v]) {
				if (visited[i]) continue;
				else {v = i; break;}
			}
		}
		for (int i = 0; i<c; i++) {
			assert(!visited[v]);
			visited[v] = 1;
			res[v] = 3;
			for (int i: graph[v]) {
				if (visited[i]) continue;
				else {v = i; break;}
			}
		}
	}


	if (a == 1) {
		res.assign(n, 3);
		vector<bool> v(n, 0);
		for (int i = 0; i<b; i++) {
			DFS(res, v, graph, 0, b);
		}

		for (int i = 0; i<n; i++) {
			if (!v[i]) {
				res[i] = 1;
				break;
			}
		}
	}


	return res;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (int i = 0; i<p.size(); i++) {
      |                  ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB ok, correct split
2 Correct 1 ms 204 KB ok, correct split
3 Correct 0 ms 204 KB ok, correct split
4 Correct 1 ms 204 KB ok, correct split
5 Correct 1 ms 204 KB ok, correct split
6 Correct 1 ms 204 KB ok, correct split
7 Correct 65 ms 8628 KB ok, correct split
8 Correct 76 ms 13856 KB ok, correct split
9 Correct 66 ms 8644 KB ok, correct split
10 Correct 61 ms 8644 KB ok, correct split
11 Correct 63 ms 8660 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB ok, correct split
2 Correct 1 ms 204 KB ok, correct split
3 Correct 1 ms 204 KB ok, correct split
4 Correct 79 ms 9884 KB ok, correct split
5 Correct 61 ms 8792 KB ok, correct split
6 Correct 73 ms 8684 KB ok, correct split
7 Correct 68 ms 12544 KB ok, correct split
8 Correct 126 ms 11068 KB ok, correct split
9 Correct 63 ms 8768 KB ok, correct split
10 Correct 80 ms 9020 KB ok, correct split
11 Correct 59 ms 9056 KB ok, correct split
12 Correct 63 ms 8992 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB ok, correct split
2 Correct 1 ms 204 KB ok, correct split
3 Correct 0 ms 204 KB ok, correct split
4 Correct 1 ms 204 KB ok, correct split
5 Correct 1 ms 204 KB ok, correct split
6 Correct 1 ms 204 KB ok, correct split
7 Correct 65 ms 8628 KB ok, correct split
8 Correct 76 ms 13856 KB ok, correct split
9 Correct 66 ms 8644 KB ok, correct split
10 Correct 61 ms 8644 KB ok, correct split
11 Correct 63 ms 8660 KB ok, correct split
12 Correct 0 ms 204 KB ok, correct split
13 Correct 1 ms 204 KB ok, correct split
14 Correct 1 ms 204 KB ok, correct split
15 Correct 79 ms 9884 KB ok, correct split
16 Correct 61 ms 8792 KB ok, correct split
17 Correct 73 ms 8684 KB ok, correct split
18 Correct 68 ms 12544 KB ok, correct split
19 Correct 126 ms 11068 KB ok, correct split
20 Correct 63 ms 8768 KB ok, correct split
21 Correct 80 ms 9020 KB ok, correct split
22 Correct 59 ms 9056 KB ok, correct split
23 Correct 63 ms 8992 KB ok, correct split
24 Incorrect 1 ms 204 KB jury found a solution, contestant did not
25 Halted 0 ms 0 KB -