Submission #1109271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109271		dsyz	JOI tour (JOI24_joitour)	C++17	0 / 100	160 ms	26556 KiB

joitour

#include <bits/stdc++.h>
#include "joitour.h"
using namespace std;
using ll = long long;
#define MAXN (200005)
ll N, Q;
ll type[MAXN];
vector<ll> v[MAXN];
ll parent[MAXN];
ll JJ[MAXN], OO[MAXN], II[MAXN];
ll jtot = 0, otot = 0, itot = 0;
ll find_set(ll x){
	if(parent[x] == x) return x;
	parent[x] = find_set(parent[x]);
	return parent[x];
}
bool same_set(ll x,ll y){
	return find_set(x) == find_set(y);
}
void merge_set(ll x,ll y){
	if(same_set(x,y)) return;
	ll totalJJ = JJ[find_set(x)] + JJ[find_set(y)];
	ll totalOO = OO[find_set(x)] + OO[find_set(y)];
	ll totalII = II[find_set(x)] + II[find_set(y)];
	parent[find_set(x)] = find_set(y);
	ll newroot = find_set(x);
	JJ[newroot] = totalJJ;
	OO[newroot] = totalOO;
	II[newroot] = totalII;
}
void init(int n, std::vector<int> F, std::vector<int> U, std::vector<int> V, int q) {
	N = n;
	Q = q;
	for(ll i = 0;i < N;i++){
		type[i] = F[i];
		if(type[i] == 0) jtot++;
		else if(type[i] == 1) otot++;
		else if(type[i] == 2) itot++;
	}
	for(ll i = 0;i < N - 1;i++){
		ll a = U[i];
		ll b = V[i];
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(ll i = 0;i < N;i++){
		parent[i] = i;
		JJ[i] = 0, OO[i] = 0, II[i] = 0;
		if(type[i] == 0) JJ[i] = 1;
		else if(type[i] == 1) OO[i] = 1;
		else if(type[i] == 2) II[i] = 1;
	}
	for(ll x = 0;x < N;x++){
		if(type[x] == 1) continue;
		for(auto u : v[x]){
			if(type[u] == 1) continue;
			if(same_set(x,u)) continue;
			merge_set(x,u);
		}
	}
}

void change(int X, int Y) {
	if(type[X] == 0) jtot--;
	else if(type[X] == 1) otot--;
	else if(type[X] == 2) itot--;
	type[X] = Y;
	if(type[X] == 0) jtot++;
	else if(type[X] == 1) otot++;
	else if(type[X] == 2) itot++;
	for(ll i = 0;i < N;i++){
		parent[i] = i;
		JJ[i] = 0, OO[i] = 0, II[i] = 0;
		if(type[i] == 0) JJ[i] = 1;
		else if(type[i] == 1) OO[i] = 1;
		else if(type[i] == 2) II[i] = 1;
	}
	for(ll x = 0;x < N;x++){
		if(type[x] == 1) continue;
		for(auto u : v[x]){
			if(type[u] == 1) continue;
			if(same_set(x,u)) continue;
			merge_set(x,u);
		}
	}
}

long long num_tours() {
	set<ll> roots;
	for(ll i = 0;i < N;i++){
		roots.insert(find_set(i));
	}
	ll ans = 0;
	for(auto i : roots){
		ans += (JJ[i] * (itot - II[i]));
	}
	return ans;
}

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