oj.uz

Submission #169822

# Submission time Handle Problem Language Result Execution time Memory
169822 2019-12-22T23:55:41 Z arthur_nascimento Split the Attractions (IOI19_split) C++14
11 / 100
 980 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 == 0){
			for(int i=0;i<n;i++) res[i] = 0;
		}
	}
	

	
	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 5084 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 4984 KB ok, correct split
6 Runtime error 954 ms 1048576 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 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 98 ms 11892 KB ok, correct split
5 Correct 148 ms 18164 KB ok, correct split
6 Correct 76 ms 10744 KB ok, correct split
7 Correct 138 ms 17560 KB ok, correct split
8 Correct 188 ms 23420 KB ok, correct split
9 Correct 119 ms 16760 KB ok, correct split
10 Correct 151 ms 21360 KB ok, correct split
11 Correct 150 ms 21260 KB ok, correct split
12 Correct 155 ms 21360 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Runtime error 166 ms 39708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 980 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 5084 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 4984 KB ok, correct split
6 Runtime error 954 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -