oj.uz

Submission #169824

# Submission time Handle Problem Language Result Execution time Memory
169824 2019-12-22T23:56:22 Z arthur_nascimento Split the Attractions (IOI19_split) C++14
11 / 100
 954 ms 1048576 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++) ans[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 4984 KB ok, correct split
2 Correct 6 ms 4984 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 6 ms 4988 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 96 ms 12916 KB ok, correct split
5 Correct 134 ms 19060 KB ok, correct split
6 Correct 76 ms 11768 KB ok, correct split
7 Correct 125 ms 18420 KB ok, correct split
8 Correct 195 ms 24168 KB ok, correct split
9 Correct 120 ms 17656 KB ok, correct split
10 Correct 158 ms 22000 KB ok, correct split
11 Correct 150 ms 22128 KB ok, correct split
12 Correct 158 ms 22260 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 Incorrect 161 ms 21236 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 Runtime error 935 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 4984 KB ok, correct split
2 Correct 6 ms 4984 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 6 ms 4988 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 -