oj.uz

Submission #169826

# Submission time Handle Problem Language Result Execution time Memory
169826 2019-12-22T23:58:08 Z arthur_nascimento Split the Attractions (IOI19_split) C++14
0 / 100
 95 ms 12012 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++)
              ~^~~~~~~~~
split.cpp:75:6: warning: unused variable 'look' [-Wunused-variable]
  int look = 1;
      ^~~~

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 5112 KB ok, correct split
4 Correct 6 ms 4984 KB ok, correct split
5 Correct 6 ms 5112 KB ok, correct split
6 Incorrect 6 ms 4984 KB 3 components are not connected
7 Halted 0 ms 0 KB -

Subtask #2
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 95 ms 12012 KB ok, correct split
5 Incorrect 73 ms 10868 KB 2 components are not connected
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB 2 components are not connected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Incorrect 6 ms 5112 KB 2 components are not connected
3 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 5112 KB ok, correct split
4 Correct 6 ms 4984 KB ok, correct split
5 Correct 6 ms 5112 KB ok, correct split
6 Incorrect 6 ms 4984 KB 3 components are not connected
7 Halted 0 ms 0 KB -