Submission #1269433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269433		MateiKing80	JOI tour (JOI24_joitour)	C++20	20 / 100	3065 ms	42548 KiB

joitour

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

using namespace std;

using ll = long long;
#define int ll

const int N = 200005, B = 19;

int n;
vector<int> vec[N];
int tip[N], subInit[3][N], stot[3];
int inNod[N], ans = 0;

void dfs(int nod, int papa) {
	subInit[0][nod] = subInit[1][nod] = subInit[2][nod] = 0;
	inNod[nod] = 0;
	for (auto i : vec[nod]) {
		if (i == papa)
			continue;
		dfs(i, nod);
		inNod[nod] += subInit[0][nod] * subInit[2][i];
		inNod[nod] += subInit[2][nod] * subInit[0][i];
		subInit[0][nod] += subInit[0][i];
		subInit[1][nod] += subInit[1][i];
		subInit[2][nod] += subInit[2][i];
	}
	subInit[tip[nod]][nod] ++;
	inNod[nod] += subInit[0][nod] * (stot[2] - subInit[2][nod]);
	inNod[nod] += subInit[2][nod] * (stot[0] - subInit[0][nod]);
}

void init(signed _N, vector<signed> F, vector<signed> U, vector<signed> V, signed Q) {
	n = _N;
	for (int i = 0; i < n; i ++) {
		tip[i] = F[i];
		stot[tip[i]] ++;
	}
	for (int i = 0; i < n - 1; i ++) {
		vec[V[i]].push_back(U[i]);
		vec[U[i]].push_back(V[i]);
	}
	dfs(0, -1);
	for (int i = 0; i < n; i ++)
		ans += (tip[i] == 1) * inNod[i];
}

void change(signed x, signed y) {
	stot[tip[x]] --;
	tip[x] = y;
	stot[tip[x]] ++;

	dfs(0, -1);
	ans = 0;
	for (int i = 0; i < n; i ++)
		ans += (tip[i] == 1) * inNod[i];
}

int num_tours() {
  return ans;
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 34
• Subtask 7: 0 / 14