oj.uz

Submission #242713

# Submission time Handle Problem Language Result Execution time Memory
242713 2020-06-29T06:24:49 Z groeneprof Split the Attractions (IOI19_split) C++14
18 / 100
 131 ms 27388 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9;

vector<int> ts, mi, size;
vector<bool> open;
vector<int> res;
vector<vector<int> > graph;
int a,b,c,n,va,vb,vc;
int na = 0, nb = 0;
int t = 0;
bool bol = false;
vector<bool> vis;
void dfs2(int u, int& mints);
void dfs3(int u);
int dfs(int u, int p){
	if(open[u]){
		return 0;
	}
	int ms = 0;
	ts[u] = t++;
	mi[u] = ts[u];
	open[u] = true;
	for(int v : graph[u]) if(v!=p){
		int s = dfs(v,u);
		size[u]+=s;
		ms = max(ms,s);
		mi[u] = min(mi[u], mi[v]);
	}
	if(size[u]>=a&&ms<a&&!bol){
		int p1 = size[u];
		vector<bool> startA(graph[u].size(),1);
		for(int i = 0; i<graph[u].size(); i++) if(graph[u][i]!=p){
			int v = graph[u][i];
			if(mi[v]<ts[u] && p1-size[v]>=a){
				p1-=size[v];
				startA[i] = false;
			}
		}
		if(n-p1>=b){
			//YES
			//A: dfs starting from children with startA[v] == true, over nodes with ts>ts[u]
			//B: then dfs starting from p, ignoring nodes that already have been chosen
			//C: default option
			res[u] = va;
			vis[u] = true;
			na = 1;
			for(int i = 0; i<graph[u].size();i++) if(startA[i]){
				dfs2(graph[u][i],ts[u]);
			}
			for(int i = 0; i<graph[u].size();i++){
				dfs3(graph[u][i]);
			}
		}
		else{
			//NO
			//res = {0,0,0,...}
			res.assign(n,0);
		}
		bol = true;
	}
	return size[u];
}


void dfs2(int u, int& mints){
	if(vis[u]||ts[u]<=mints||na>=a){
		return;
	}
	res[u] = va;
	na++;
	vis[u] = true;
	for(int v : graph[u]) {
		dfs2(v,mints);
	}
}

void dfs3(int u){
	if(vis[u]||nb>=b){
		return;
	}
	res[u] = vb;
	nb++;
	vis[u] = true;
	for(int v : graph[u]){
		dfs3(v);
	}
}

vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
	pair<int,int> d[3] = {{A,1},{B,2},{C,3}};
	n = N;
	sort(d, d+3);
	a = d[0].first; b = d[1].first; c = d[2].first;
	va = d[0].second; vb = d[1].second; vc = d[2].second;


	graph.resize(n);
	ts.resize(n,-1);
	mi.resize(n,inf);
	size.resize(n,1);
	vis.resize(n,false);
	open.resize(n, false);
	res.resize(n,vc);

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

Compilation message

split.cpp: In function 'int dfs(int, int)':
split.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i<graph[u].size(); i++) if(graph[u][i]!=p){
                  ~^~~~~~~~~~~~~~~~
split.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i<graph[u].size();i++) if(startA[i]){
                   ~^~~~~~~~~~~~~~~~
split.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i<graph[u].size();i++){
                   ~^~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:107:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<p.size();i++){
                 ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB ok, correct split
2 Correct 4 ms 256 KB ok, correct split
3 Correct 5 ms 256 KB ok, correct split
4 Correct 5 ms 256 KB ok, correct split
5 Correct 5 ms 384 KB ok, correct split
6 Correct 5 ms 384 KB ok, correct split
7 Correct 117 ms 26360 KB ok, correct split
8 Correct 108 ms 21496 KB ok, correct split
9 Correct 109 ms 19960 KB ok, correct split
10 Correct 97 ms 27256 KB ok, correct split
11 Correct 131 ms 27256 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB ok, correct split
2 Correct 5 ms 256 KB ok, correct split
3 Correct 5 ms 256 KB ok, correct split
4 Correct 114 ms 19064 KB ok, correct split
5 Correct 81 ms 10104 KB ok, correct split
6 Correct 102 ms 27388 KB ok, correct split
7 Correct 102 ms 22648 KB ok, correct split
8 Correct 131 ms 12408 KB ok, correct split
9 Correct 83 ms 10232 KB ok, correct split
10 Correct 59 ms 10480 KB ok, correct split
11 Correct 59 ms 10480 KB ok, correct split
12 Correct 60 ms 10480 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB ok, correct split
2 Incorrect 82 ms 10104 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB ok, correct split
2 Correct 5 ms 256 KB ok, no valid answer
3 Correct 4 ms 256 KB ok, correct split
4 Correct 5 ms 256 KB ok, correct split
5 Correct 5 ms 384 KB ok, correct split
6 Correct 5 ms 256 KB ok, correct split
7 Correct 5 ms 256 KB ok, correct split
8 Correct 5 ms 384 KB ok, correct split
9 Correct 7 ms 768 KB ok, correct split
10 Correct 7 ms 640 KB ok, correct split
11 Correct 5 ms 384 KB ok, correct split
12 Correct 7 ms 768 KB ok, correct split
13 Correct 5 ms 256 KB ok, correct split
14 Correct 4 ms 256 KB ok, correct split
15 Correct 5 ms 384 KB ok, correct split
16 Correct 5 ms 256 KB ok, correct split
17 Correct 5 ms 256 KB ok, correct split
18 Correct 5 ms 256 KB ok, correct split
19 Correct 5 ms 384 KB ok, correct split
20 Correct 6 ms 512 KB ok, correct split
21 Correct 6 ms 768 KB ok, correct split
22 Incorrect 6 ms 640 KB jury found a solution, contestant did not
23 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB ok, correct split
2 Correct 4 ms 256 KB ok, correct split
3 Correct 5 ms 256 KB ok, correct split
4 Correct 5 ms 256 KB ok, correct split
5 Correct 5 ms 384 KB ok, correct split
6 Correct 5 ms 384 KB ok, correct split
7 Correct 117 ms 26360 KB ok, correct split
8 Correct 108 ms 21496 KB ok, correct split
9 Correct 109 ms 19960 KB ok, correct split
10 Correct 97 ms 27256 KB ok, correct split
11 Correct 131 ms 27256 KB ok, correct split
12 Correct 5 ms 384 KB ok, correct split
13 Correct 5 ms 256 KB ok, correct split
14 Correct 5 ms 256 KB ok, correct split
15 Correct 114 ms 19064 KB ok, correct split
16 Correct 81 ms 10104 KB ok, correct split
17 Correct 102 ms 27388 KB ok, correct split
18 Correct 102 ms 22648 KB ok, correct split
19 Correct 131 ms 12408 KB ok, correct split
20 Correct 83 ms 10232 KB ok, correct split
21 Correct 59 ms 10480 KB ok, correct split
22 Correct 59 ms 10480 KB ok, correct split
23 Correct 60 ms 10480 KB ok, correct split
24 Correct 5 ms 384 KB ok, correct split
25 Incorrect 82 ms 10104 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -