Submission #596258

#	Time	Username	Problem	Language	Result	Execution time	Memory
596258		alireza_kaviani	Split the Attractions (IOI19_split)	C++17	40 / 100	284 ms	20048 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define SZ(x)	ll((x).size())
#define X 		first
#define Y 		second
#define all(x)	(x).begin() , (x).end()

const int MAXN = 2e5 + 10;

int n , m , A[3] , C[3] , mark[MAXN] , sz[MAXN] , par[MAXN] , col[MAXN] , intree[MAXN];
vector<pii> adj[MAXN];

void DFS(int v){
	mark[v] = sz[v] = 1;
	for(pii i : adj[v]){
		int u = i.X , ind = i.Y;
		if(mark[u])	continue;
		par[u] = v; intree[ind] = 1;
		DFS(u);
		sz[v] += sz[u];
	}
}

void SolveDFS(int v , int p , int color){
	if(A[color] == 0)	return;
	A[color]--;
	col[v] = C[color];
	for(pii i : adj[v]){
		int u = i.X , ind = i.Y;
		if(intree[ind] == 0 || u == p)	continue;
		SolveDFS(u , v , color);
	}
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n = N; m = SZ(p); A[0] = a; A[1] = b; A[2] = c;
	C[0] = 1; C[1] = 2; C[2] = 3;
	for(int i = 0 ; i < 3 ; i++){
		for(int j = 0 ; j < 2 ; j++){
			if(A[i] > A[i + 1]){
				swap(A[i] , A[i + 1]);
				swap(C[i] , C[i + 1]);
			}
		}
	}

	for(int i = 0 ; i < m ; i++){
		int v = p[i] , u = q[i];
		adj[v].push_back({u , i});
		adj[u].push_back({v , i});
	}

	int flag = 0;
	srand(645674156);
	for(int _ = 0 ; _ < 20 ; _++){
		memset(mark , 0 , sizeof(mark));
		memset(sz , 0 , sizeof(sz));
		memset(par , 0 , sizeof(par));
		memset(intree , 0 , sizeof(intree));
		for(int i = 0 ; i < n ; i++){
			random_shuffle(all(adj[i]));
		}
		int root = rand() % n;
		DFS(root);
		for(int i = 0 ; i < n ; i++){
			if(i == root)	continue;
			if(A[0] <= sz[i] && sz[i] <= n - A[0]){
				if(sz[i] <= n / 2){
					SolveDFS(i , par[i] , 0);
					SolveDFS(par[i] , i , 1);
				}
				else{
					SolveDFS(par[i] , i , 0);
					SolveDFS(i , par[i] , 1);
				}
				flag = 1;
				break;
			}
		}
		if(flag){
			break;
		}
	}

	vector<int> res;
	for(int i = 0 ; i < n ; i++){
		if(flag == 0){
			res.push_back(0);
		}
		else if(col[i]){
			res.push_back(col[i]);
		}
		else{
			res.push_back(C[2]);
		}
	}

	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:45:21: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
   45 |    if(A[i] > A[i + 1]){
      |              ~~~~~~~^
split.cpp:43:20: note: within this loop
   43 |  for(int i = 0 ; i < 3 ; i++){
      |                  ~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36