oj.uz

Submission #1072271

# Submission time Handle Problem Language Result Execution time Memory
1072271 2024-08-23T16:13:45 Z NeroZein The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 99 ms 14184 KB 
#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]) {
					//~ cerr << "u, v: " << u << ' ' << v << endl; 
					ties[u] = 1; 
				}
				dfs2(u, v); 
			}
		}
	};
	for (int i = 0; i < n; ++i) {
		if (g[i].size() == 2) {
			dfs2(i, i);
			//~ cerr << "i, :" << i << endl; 
			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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 768 KB Correct

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 14184 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 7776 KB Correct
2 Incorrect 89 ms 7768 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 768 KB Correct
2 Incorrect 99 ms 14184 KB Not correct
3 Halted 0 ms 0 KB -