Submission #1271626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271626		MateiKing80	The Ties That Guide Us (CEOI23_incursion)	C++20	100 / 100	161 ms	6904 KiB

incursion

#include "incursion.h"
#include <bits/stdc++.h>

using namespace std;

const int NM = 50000;
vector<int> vec[NM];
int sz[NM], papa[NM];

void dfs(int nod, int tata) {
	papa[nod] = tata;
	sz[nod] = 1;
	for (auto &i : vec[nod]) {
		if (i == tata)
			continue;
		dfs(i, nod);
		sz[nod] += sz[i];
	}
}

int find_centroid(int nod, int papa1, int target) {
	for (auto i : vec[nod]) {
		if (i == papa1)
			continue;
		if (sz[i] >= target)
			return find_centroid(i, nod, target);
	}
	return nod;
}

vector<int> mark(vector<pair<int, int>> vp, int seif) {
	int n = vp.size() + 1;
	for (auto [u, v] : vp) {
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	dfs(1, 0);
	int c = find_centroid(1, 0, (sz[1] + 1) / 2);
	dfs(c, 0);
	vector<int> ans(n);
	ans[seif - 1] = 1;
	while (seif != c) {
		seif = papa[seif];
		ans[seif - 1] = 1;
	}
	int c2 = -1;
	for (auto i : vec[c]) {
		if (sz[i] == (n + 1) / 2) {
			c2 = i;
		}
	}
	if (c2 != -1 && ans[c2 - 1] == 1)
		ans[c - 1] = 0;
	return ans;
}

void locate(vector<pair<int, int>> vp, int pos, int nrt) {
	int n = vp.size() + 1;
	for (int i = 1; i <= n; i ++)
		vec[i].clear();
	for (auto [u, v] : vp) {
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	dfs(1, 0);
	int c = find_centroid(1, 0, (sz[1] + 1) / 2);
	dfs(c, 0);
	int c2 = -1;
	for (auto i : vec[c]) {
		if (sz[i] == (n + 1) / 2) {
			c2 = i;
		}
	}
	if (c2 == -1) {
		vec[c].push_back(c);
	}
	for (int i = 1; i <= n; i ++)
		sort(vec[i].begin(), vec[i].end(), [&] (int a, int b) {
			return sz[a] > sz[b];
		});
	while (nrt == 0) {
		nrt = visit(vec[pos][0]);
		pos = vec[pos][0];
	}
	while (1) {	//de acu incep in jos
		bool ok = 0;
		for (int i = 1; i < (int)vec[pos].size(); i ++) { 
			int nrtt = visit(vec[pos][i]);
			if (nrtt == 0) {
				visit(pos);
			} else {
				ok = 1;
				pos = vec[pos][i];
				nrt = nrtt;
				break;
			}
		}
		if (!ok) {
			break;
		}
	}
}

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40