oj.uz

Submission #169828

# Submission time Handle Problem Language Result Execution time Memory
169828 2019-12-22T23:58:37 Z arthur_nascimento Split the Attractions (IOI19_split) C++14
33 / 100
 1000 ms 1048580 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define debug  
#define ll long long
#define maxn 200200
#define pii pair<int,int>

using namespace std;

int sz[3];
int id0,id1,id2;
int ans[maxn];
vector<int> L[maxn];

int vis[maxn];


map<pii,int> bad;

int color(int vx,int qtd,int to){
	//qtd--;
	//ans[vx] = to; debug("+%d\n",vx);
	queue<int> Q;
	Q.push(vx);
	vis[vx] = 1;
	while(qtd){
		int nov = Q.front();
		Q.pop();
		ans[nov] = to;debug("+%d\n",nov);
		qtd--;
		for(int i=0;i<L[nov].size();i++){
			int yy = L[nov][i];
			if(bad[pii(nov,yy)]) continue;
			if(!vis[yy]){
				vis[yy] = 1; debug("push %d\n",yy);
				Q.push(yy);
			}
		}
	
	}
}

int pai[maxn];
int sub[maxn];
void dfs(int vx,int p=-1){
	pai[vx] = p;
	sub[vx] = 1;
	for(int i=0;i<L[vx].size();i++)
		if(L[vx][i] != p){
			dfs(L[vx][i],vx);
			sub[vx] += sub[L[vx][i]];
		}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	
	sz[0] = a;
	sz[1] = b;
	sz[2] = c;
	
	vector<int> res;
	for(int i=0;i<p.size();i++)
		L[p[i]].pb(q[i]), L[q[i]].pb(p[i]);
	
	vector<pii> vv;
	for(int i=0;i<3;i++){
		vv.pb(pii(sz[i],i));
	}
	sort(vv.begin(),vv.end());
	id0 = vv[0].second;
	id1 = vv[1].second;
	id2 = vv[2].second;
	int look = 1;
	for(int i=0;i<n;i++) ans[i] = id2+1;
	
	if(sz[id0] == 1){
		color(0,sz[id1],id1+1);
		for(int i=0;i<n;i++)
			if(ans[i] == id2+1){
				ans[i] = id0+1;
				break;
			}
	}
	else {
		dfs(0);
		
		for(int i=0;i<n && look;i++)
			if(sub[i] >= a && sub[i] <= n-a){
				bad[pii(i,pai[i])] = bad[pii(pai[i],i)] = 1;
				if(2*sub[i] <= n) {
					color(i,sz[id0],id0+1);
					color(pai[i],sz[id1],id1+1);
				}
				else {
					color(pai[i],sz[id0],id0+1);
					color(i,sz[id1],id1+1);
				}
				look = 0;
			}
		if(look == 1){
			for(int i=0;i<n;i++) ans[i] = 0;
		}
	}
	
	//for(int i=0;i<a;i++) ans[i] = 1;
	///for(int i=a;i<a+b;i++) ans[i] = 2;
	//for(int i=a+b;i<n;i++) ans[i] = 3;
	
	for(int i=0;i<n;i++) res.pb(ans[i]);
	return res;
}

Compilation message

split.cpp: In function 'int color(int, int, int)':
split.cpp:31:31: warning: left operand of comma operator has no effect [-Wunused-value]
   ans[nov] = to;debug("+%d\n",nov);
                               ^~~
split.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<L[nov].size();i++){
               ~^~~~~~~~~~~~~~
split.cpp:37:36: warning: left operand of comma operator has no effect [-Wunused-value]
     vis[yy] = 1; debug("push %d\n",yy);
                                    ^~
split.cpp:43:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
split.cpp: In function 'void dfs(int, int)':
split.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<L[vx].size();i++)
              ~^~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();i++)
              ~^~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 6 ms 5112 KB ok, correct split
3 Correct 6 ms 5112 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 6 ms 5112 KB ok, correct split
6 Runtime error 945 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 6 ms 5112 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 93 ms 11892 KB ok, correct split
5 Correct 129 ms 18164 KB ok, correct split
6 Correct 75 ms 11384 KB ok, correct split
7 Correct 120 ms 18008 KB ok, correct split
8 Correct 182 ms 24240 KB ok, correct split
9 Correct 115 ms 17400 KB ok, correct split
10 Correct 145 ms 21616 KB ok, correct split
11 Correct 144 ms 21744 KB ok, correct split
12 Correct 151 ms 21844 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 152 ms 20996 KB ok, correct split
3 Correct 34 ms 8416 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 152 ms 22840 KB ok, correct split
6 Correct 152 ms 22644 KB ok, correct split
7 Correct 152 ms 22644 KB ok, correct split
8 Correct 155 ms 23536 KB ok, correct split
9 Correct 153 ms 22516 KB ok, correct split
10 Correct 29 ms 7804 KB ok, no valid answer
11 Correct 41 ms 9080 KB ok, no valid answer
12 Correct 71 ms 13172 KB ok, no valid answer
13 Correct 84 ms 12944 KB ok, no valid answer
14 Correct 68 ms 13296 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1000 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 6 ms 5112 KB ok, correct split
3 Correct 6 ms 5112 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 6 ms 5112 KB ok, correct split
6 Runtime error 945 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -