Submission #1052045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052045		rainboy	The Ties That Guide Us (CEOI23_incursion)	C++17	40 / 100	220 ms	13204 KiB

incursion

#include "incursion.h"
#include <cstdlib>
#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], eo[N], n;

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

	void init(vpi ij) {
		n = ij.size() + 1;
		for (int i = 0; i < n; i++)
			ej[i] = (int *) malloc(3 * sizeof *ej[i]), eo[i] = 0;
		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 cc[N];

	void dfs(int p, int i, int c) {
		cc[i] = c;
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (j != p)
				dfs(i, j, (c + 1) % 3);
		}
	}

	void cleanup() {
		for (int i = 0; i < n; i++)
			free(ej[i]);
	}
}

vi mark(vpi ij, int s) {
	A::init(ij), s--;
	A::dfs(-1, s, 0);
	vi cc(A::n);
	for (int i = 0; i < A::n; i++)
		cc[i] = A::cc[i];
	A::cleanup();
	return cc;
}

namespace B {
	const int N = 45000;

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

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

	void init(vpi ij) {
		n = ij.size() + 1;
		for (int i = 0; i < n; i++)
			ej[i] = (int *) malloc(3 * sizeof *ej[i]), eo[i] = 0;
		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 sz[N];

	void dfs(int p, int i) {
		sz[i] = 1;
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (j != p) {
				dfs(i, j);
				sz[i] += sz[j];
			}
		}
	}

	unsigned int Z = 12345;

	int rand_() {
		return (Z *= 3) >> 1;
	}

	void sort(int *ii, int l, int r) {
		while (l < r) {
			int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

			while (j < k)
				if (sz[ii[j]] == sz[i_])
					j++;
				else if (sz[ii[j]] < sz[i_]) {
					tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
					i++, j++;
				} else {
					k--;
					tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
				}
			sort(ii, l, i);
			l = k;
		}
	}

	void cleanup() {
		for (int i = 0; i < n; i++)
			free(ej[i]);
	}
}

void locate(vpi ij, int i, int c) {
	B::init(ij), i--;
	int p = -1;
	B::dfs(-1, i);
	while (1) {
		B::sort(B::ej[i], 0, B::eo[i]);
		bool found = false;
		for (int o = B::eo[i]; o--; ) {
			int j = B::ej[i][o];
			if (j != p) {
				if ((visit(j + 1) + 1) % 3 == c) {
					found = true, p = i, i = j, c = (c + 2) % 3;
					break;
				}
				visit(i + 1);
			}
		}
		if (!found)
			break;
	}
	B::cleanup();
}

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: 12 / 30
• Subtask 2: 12 / 30
• Subtask 3: 16 / 40