oj.uz

Submission #169821

# Submission time Handle Problem Language Result Execution time Memory
169821 2019-12-22T23:54:16 Z arthur_nascimento Split the Attractions (IOI19_split) C++14
11 / 100
 1014 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;
	
	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;
	
	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);
		int look = 1;
		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;
			}
	}
	
	vector<int> res;
	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:63: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 4984 KB ok, correct split
4 Correct 6 ms 4984 KB ok, correct split
5 Correct 6 ms 5112 KB ok, correct split
6 Runtime error 942 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 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 96 ms 12020 KB ok, correct split
5 Correct 128 ms 18420 KB ok, correct split
6 Correct 74 ms 10972 KB ok, correct split
7 Correct 126 ms 17652 KB ok, correct split
8 Correct 182 ms 23520 KB ok, correct split
9 Correct 117 ms 16936 KB ok, correct split
10 Correct 144 ms 21488 KB ok, correct split
11 Correct 141 ms 21588 KB ok, correct split
12 Correct 148 ms 21488 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 144 ms 20304 KB ok, correct split
3 Correct 34 ms 8568 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 156 ms 22892 KB ok, correct split
6 Correct 148 ms 22644 KB ok, correct split
7 Correct 183 ms 22644 KB ok, correct split
8 Correct 190 ms 23412 KB ok, correct split
9 Correct 195 ms 22600 KB ok, correct split
10 Incorrect 33 ms 7800 KB invalid split: #1=0, #2=0, #3=33333
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

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