oj.uz

Submission #156499

# Submission time Handle Problem Language Result Execution time Memory
156499 2019-10-06T08:38:44 Z MoNsTeR_CuBe Split the Attractions (IOI19_split) C++17
11 / 100
 115 ms 12636 KB 
#include "split.h"
#include <bits/stdc++.h>
 
using namespace std;
 
vector< vector< int > > Graph;

vector< int > colouring;

vector< bool > visited;

int remaining;

void dfs(int node){
	visited[node] = true;
	
	if(remaining){
		remaining--;
		 colouring[node] = 2;
	}
	
	for(int a : Graph[node]){
		if(visited[a]) continue;
		dfs(a);
	}
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	
	Graph.resize(N);
	colouring.resize(N);
	visited.assign(N, false);
	
	remaining = b;
		
	for(int i = 0; i < (int)p.size(); i++){
		Graph[p[i]].push_back(q[i]);
		Graph[q[i]].push_back(p[i]);
	}
	
	dfs(0);
	
	for(int i = 0; i < N; i++){
		if(colouring[i] == 2) continue;
		if(a){
			a--;
			colouring[i] = 1;
		} 
		else colouring[i] = 3;
	}
	
	return colouring;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 2 ms 256 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 256 KB ok, correct split
5 Correct 2 ms 256 KB ok, correct split
6 Incorrect 2 ms 376 KB 2 components are not connected
7 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB ok, correct split
2 Correct 2 ms 256 KB ok, correct split
3 Correct 2 ms 380 KB ok, correct split
4 Correct 96 ms 12536 KB ok, correct split
5 Correct 79 ms 9452 KB ok, correct split
6 Correct 77 ms 12460 KB ok, correct split
7 Correct 80 ms 11336 KB ok, correct split
8 Correct 115 ms 12636 KB ok, correct split
9 Correct 80 ms 9464 KB ok, correct split
10 Correct 60 ms 9328 KB ok, correct split
11 Correct 57 ms 9408 KB ok, correct split
12 Correct 60 ms 9712 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Incorrect 75 ms 9436 KB 2 components are not connected
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 296 KB 2 components are not connected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 2 ms 256 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 256 KB ok, correct split
5 Correct 2 ms 256 KB ok, correct split
6 Incorrect 2 ms 376 KB 2 components are not connected
7 Halted 0 ms 0 KB -