Submission #1053265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053265		rainboy	The Ties That Guide Us (CEOI23_incursion)	C++17	100 / 100	222 ms	11064 KiB

incursion

#include "incursion.h"
#include <cstring>
#include <vector>

using namespace std;

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

namespace A {
	const int N = 45000;

	int ej[N][3], eo[N], n;

	void append(int i, int j) {
		ej[i][eo[i]++] = j;
	}

	void init(vpi ij) {
		n = ij.size() + 1;
		memset(eo, 0, n * sizeof *eo);
		for (int h = 0; h < n - 1; h++) {
			int i = ij[h].first - 1, j = ij[h].second - 1;
			append(i, j), append(j, i);
		}
	}

	int pp[N], sz[N], c1, c2;

	void dfs1(int p, int i) {
		sz[i] = 1;
		bool centroid = true;
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (j != p) {
				dfs1(i, j);
				sz[i] += sz[j];
				if (sz[j] * 2 > n)
					centroid = false;
			}
		}
		if ((n - sz[i]) * 2 > n)
			centroid = false;
		if (centroid) {
			if (c1 == -1)
				c1 = i;
			else
				c2 = i;
		}
	}

	void dfs2(int p, int i) {
		pp[i] = p;
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (j != p)
				dfs2(i, j);
		}
	}
}

vi mark(vpi ij, int t) {
	A::init(ij), t--;
	A::c1 = A::c2 = -1, A::dfs1(-1, t);
	if (A::c2 == -1)
		A::dfs2(-1, A::c1);
	else
		A::dfs2(A::c2, A::c1), A::dfs2(A::c1, A::c2);
	vi cc(A::n, 0);
	while (t != A::c1 && t != A::c2)
		cc[t] = 1, t = A::pp[t];
	cc[t] = 1;
	return cc;
}

namespace B {
	const int N = 45000;

	int ej[N][3], eo[N], n;

	void append(int i, int j) {
		ej[i][eo[i]++] = j;
	}

	void init(vpi ij) {
		n = ij.size() + 1;
		memset(eo, 0, n * sizeof *eo);
		for (int h = 0; h < n - 1; h++) {
			int i = ij[h].first - 1, j = ij[h].second - 1;
			append(i, j), append(j, i);
		}
	}

	int pp[N], sz[N], c1, c2;

	void dfs1(int p, int i) {
		sz[i] = 1;
		bool centroid = true;
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (j != p) {
				dfs1(i, j);
				sz[i] += sz[j];
				if (sz[j] * 2 > n)
					centroid = false;
			}
		}
		if ((n - sz[i]) * 2 > n)
			centroid = false;
		if (centroid) {
			if (c1 == -1)
				c1 = i;
			else
				c2 = i;
		}
	}

	void dfs2(int p, int i) {
		pp[i] = p;
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (j != p)
				dfs2(i, j);
		}
	}
}

void locate(vpi ij, int s, int c) {
	B::init(ij), s--;
	B::c1 = B::c2 = -1, B::dfs1(-1, s);
	if (B::c2 == -1)
		B::dfs2(-1, B::c1);
	else
		B::dfs2(B::c2, B::c1), B::dfs2(B::c1, B::c2);
	int i = s, q = -1;
	while (c == 0)
		q = i, c = visit((i = B::pp[i]) + 1);
	while (1) {
		int j1 = -1, j2 = -1, j3 = -1, tmp;
		for (int o = B::eo[i]; o--; ) {
			int j = B::ej[i][o];

			if (j != B::pp[i] && j != q) {
				if (j1 == -1)
					j1 = j;
				else if (j2 == -1)
					j2 = j;
				else
					j3 = j;
			}
		}
		if (j1 == -1 || j2 != -1 && B::sz[j1] < B::sz[j2])
			tmp = j1, j1 = j2, j2 = tmp;
		if (j1 == -1 || j3 != -1 && B::sz[j1] < B::sz[j3])
			tmp = j1, j1 = j3, j3 = tmp;
		if (j2 == -1 || j3 != -1 && B::sz[j2] < B::sz[j3])
			tmp = j2, j2 = j3, j3 = tmp;
		if (j1 != -1) {
			if (visit(j1 + 1)) {
				i = j1;
				continue;
			}
			visit(i + 1);
		}
		if (j2 != -1) {
			if (visit(j2 + 1)) {
				i = j2;
				continue;
			}
			visit(i + 1);
		}
		if (j3 != -1) {
			if (visit(j3 + 1)) {
				i = j3;
				continue;
			}
			visit(i + 1);
		}
		break;
	}
}

Compilation message (stderr)

incursion.cpp: In function 'void locate(vpi, int, int)':
incursion.cpp:153:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  153 |   if (j1 == -1 || j2 != -1 && B::sz[j1] < B::sz[j2])
      |                   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
incursion.cpp:155:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  155 |   if (j1 == -1 || j3 != -1 && B::sz[j1] < B::sz[j3])
      |                   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
incursion.cpp:157:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  157 |   if (j2 == -1 || j3 != -1 && B::sz[j2] < B::sz[j3])
      |                   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40