Submission #1072272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072272		NeroZein	The Ties That Guide Us (CEOI23_incursion)	C++17	0 / 100	93 ms	20576 KiB

incursion

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

using namespace std; 

vector<int> mark(vector<pair<int, int>> F, int safe) {
	safe--;
	int n = (int) F.size() + 1;;
	vector<vector<int>> g(n);
	for (int i = 0; i < n - 1; ++i) {
		auto [u, v] = F[i];
		--u, --v;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	vector<int> dist(n); 
	function<void(int, int)> dfs = [&](int v, int p) {
		for (int u : g[v]) {
			if (u != p) {
				dist[u] = dist[v] + 1; 
				dfs(u, v); 
			}
		}
	};
	dfs(safe, safe); 
	vector<int> ties(n); 
	function<void(int, int)> dfs2 = [&](int v, int p) {
		for (int u : g[v]) {
			if (u != p) {
				if (dist[v] < dist[u]) {
					ties[u] = 1; 
				}
				dfs2(u, v); 
			}
		}
	};
	for (int i = 0; i < n; ++i) {
		if (g[i].size() == 2) {
			dfs2(i, i);
			break; 
		}
	}
	return ties; 
}

void locate(vector<pair<int, int>> F, int curr, int t) {
	--curr;
	int n = (int) F.size() + 1; 
	vector<vector<int>> g(n); 
	for (int i = 0; i < n - 1; ++i) {
		auto [u, v] = F[i];
		--u, --v; 
		g[u].push_back(v);
		g[v].push_back(u); 
	} 
	vector<int> sz(n);
	vector<int> pr(n, -1);
	function<void(int, int)> dfs = [&](int v, int p) {
		sz[v] = 1;
		for (int u : g[v]) {
			if (u != p) {
				pr[u] = v;
				dfs(u, v);
				sz[v] += sz[u]; 
			}
		}
	};
	for (int i = 0; i < n; ++i) {
		if (g[i].size() == 2) {
			dfs(i, i); 
			break;
		}
	}
	function<void(int, int, int)> dfs2 = [&](int v, int p, int tt) {
		if (tt == 1) {
			assert(pr[v] != p && pr[v] != -1); 
			int x = visit(pr[v] + 1);
			return dfs2(pr[v], v, x);
		}
		sort(g[v].begin(), g[v].end(), [&](int i, int j) {
			return sz[g[v][i]] > sz[g[v][j]];
		});
		for (int u : g[v]) {
			if (u == pr[v] || u == p) continue; 
			int x = visit(u + 1);
			if (x == 1) {
				visit(v + 1);
			} else {
				return dfs2(u, v, x); 
			}
		}
	};
	dfs2(curr, curr, t);
}

Compilation message (stderr)

interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~

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