Submission #144016

#	Time	Username	Problem	Language	Result	Execution time	Memory
144016		tincamatei	Split the Attractions (IOI19_split)	C++14	0 / 100	4 ms	2680 KiB

split

#include "split.h"
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAX_N = 100000;
const int MAX_M = 200000;

int lastid;
int low[MAX_N], id[MAX_N];
int depth[MAX_N];
bool critic[MAX_N];

struct Edge {
	int a, b;

	int other(int x) {
		return a ^ b ^ x;
	}
} edges[MAX_M];

vector<int> graph[MAX_N];

void dfs(int nod, int fatherEdge, int d) {
	int bico = 0;
	low[nod] = id[nod] = ++lastid;
	depth[nod] = d;
	for(auto it: graph[nod]) {
		int son = edges[it].other(nod);

		if(it != fatherEdge && id[son] == 0) {
			dfs(son, it, d + 1);
			low[nod] = min(low[nod], low[son]);
			if(low[son] >= id[nod]) {
				critic[nod] = true;
				++bico;
			}
		} else if(it != fatherEdge && depth[son] < depth[nod])
			low[nod] = min(low[nod], id[son]);
	}

	if(nod == 0 && bico <= 1)
		critic[nod] = false;
}

vector<int> rez;

void dfs(int nod, int &rem, int color, int papa) {
	if(rem > 0) {
		rem--;
		rez[nod] = color;
	} else
		rez[nod] = 3;

	printf("%d\n", nod);

	for(auto it: graph[nod]) {
		int son = edges[it].other(nod);
		if(son != papa && rez[son] == 0) {
			dfs(son, rem, color, nod);
		}
	}
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	rez.resize(N, 0);
	for(int i = 0; i < p.size(); ++i) {
		edges[i].a = p[i];
		edges[i].b = q[i];
		
		graph[p[i]].push_back(i);
		graph[q[i]].push_back(i);
	}

	dfs(0, -1, 0);

	int i = 0;
	while(critic[i])
		++i;

	rez[i] = 1;
	dfs(edges[graph[i][0]].other(i), b, 2, -1);
	return rez;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:68:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < p.size(); ++i) {
                 ~~^~~~~~~~~~

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