oj.uz

Submission #427594

# Submission time Handle Problem Language Result Execution time Memory
427594 2021-06-14T17:34:21 Z dreezy Split the Attractions (IOI19_split) C++17
11 / 100
 119 ms 10400 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int maxn = 1e5 + 5;
vector<int> graph[maxn];
int a, b, c;
//assume a is smallest
//assume b is second smallest

vector<int> ans;
int cnt = 0;
vector<bool> vis;
bool dfs(int n){
	cnt++;
	vis[n] = true;
	ans[n] = 2;
	if(cnt == b){
		return true;
	}
	for(int adj : graph[n]){
		if(vis[adj]) continue;
		if(dfs(adj))
			return true;
	}
	
	
	return cnt == b;
}



vector<int> find_split(int n, int a_, int b_, int c_, vector<int> p, vector<int> q) {
	
	
	a = a_;
	b = b_;
	c = c_;
	int m = p.size();
	ans.assign(n, 3);
	vis.assign(n, 0);

	for(int i =0; i<m ;i++){
		//cout << p[i] <<", "<<q[i]<<endl; 
		graph[p[i]].pb(q[i]);
		graph[q[i]].pb(p[i]);
	}
	
	if(b)
		dfs(0);
	
	for(int i =0; i<n ;i++){
		if (ans[i] == 3){
			ans[i] = 1;
			break;
		}
	}
	return ans;
	
	
}


/************/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB ok, correct split
2 Correct 2 ms 2636 KB ok, correct split
3 Correct 2 ms 2636 KB ok, correct split
4 Incorrect 2 ms 2636 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB ok, correct split
2 Correct 2 ms 2636 KB ok, correct split
3 Correct 2 ms 2636 KB ok, correct split
4 Correct 80 ms 9196 KB ok, correct split
5 Correct 63 ms 8132 KB ok, correct split
6 Correct 58 ms 8032 KB ok, correct split
7 Correct 64 ms 9572 KB ok, correct split
8 Correct 119 ms 10400 KB ok, correct split
9 Correct 67 ms 9268 KB ok, correct split
10 Correct 73 ms 9260 KB ok, correct split
11 Correct 63 ms 9288 KB ok, correct split
12 Correct 53 ms 9580 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB invalid split: #1=1, #2=1, #3=3
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB invalid split: #1=1, #2=2, #3=6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB ok, correct split
2 Correct 2 ms 2636 KB ok, correct split
3 Correct 2 ms 2636 KB ok, correct split
4 Incorrect 2 ms 2636 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -