Submission #1194862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194862		dadas08	JOI tour (JOI24_joitour)	C++20	6 / 100	221 ms	24628 KiB

joitour

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//	mt19937 engine((unsigned ll)time(NULL));
//	uniform_int_distribution<ll> distribution(0, (ll)1e18);
//	auto generator = bind(distribution, engine);
//	ll x = generator();
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
// #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vl = std::vector<ll>;
using vii = std::vector<pair<int, int> >;
using vvl = std::vector<vl>;
using vll = std::vector<pair<ll , ll> >;
using vd = std::vector<double>;
using vvd = std::vector<vd>;
using vs = std::vector<std::string>;
using vvs = std::vector<vs>;
using vb = std::vector<bool>;
using vvb = std::vector<vb>;
using vc = std::vector<char>;
using vvc = std::vector<vc>;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using piil = std::pair<pair<int, int>, ll>;
using mii = std::map<int, int>;
using mll = std::map<ll, ll>;
using pql = std::priority_queue<ll>;
using pqi = std::priority_queue<int>;
using pqiil = std::priority_queue<pair<pair<int, int>, ll> >;
using pqii = std::priority_queue<pair<int, int> >;

#define pb push_back
#define ps push
#define eb emplace_back
#define is insert
#define er erase
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define sf(i) sizeof(i)
#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define rep(i, L, R) for(ll i = L;i<=R;i++)
#define pcis precision
#define sz(a) ((ll) a.size())

template<typename T>
struct infinity {
	static constexpr T max=std::numeric_limits<T>::max();
	static constexpr T min=std::numeric_limits<T>::min();
	static constexpr T value=std::numeric_limits<T>::max()/2;
	static constexpr T mvalue=std::numeric_limits<T>::min()/2;
};
template<typename T>constexpr T INF=infinity<T>::value;
constexpr ll lINF=INF<ll>;
constexpr int iINF = INF<int>;
constexpr ld PI = 3.1415926535897932384626;

#include "joitour.h"

struct Fenwick {
	int n;
	vector<ll> f;
	void init(int _n) {
		n = _n;
		f.assign(n+1, 0);
	}
	// add v at index i (0-based)
	void update(int i, ll v) {
		for (int x = i+1; x <= n; x += x & -x)
			f[x] += v;
	}
	// sum on [0..i]
	ll query(int i) const {
		ll s = 0;
		for (int x = i+1; x > 0; x -= x & -x)
			s += f[x];
		return s;
	}
	// sum on [l..r]
	ll range_sum(int l, int r) const {
		if (l > r) return 0;
		return query(r) - (l>0 ? query(l-1) : 0);
	}
};

int N, Q;
vector<vector<int>> adj;
vector<int> F;
vector<int> tin, tout, parent;
int timer;
Fenwick bitJ, bitI;
ll totJ=0, totI=0, totO=0;
vector<ll> sg;
ll ans = 0;

// build Euler tour indices and parent[], iterative DFS
void build_euler() {
	tin.assign(N, 0);
	tout.assign(N, 0);
	parent.assign(N, -1);
	timer = 0;
	// stack of (u, parent, state, next_child_index)
	struct Item {
		int u, p, state, idx;
	};
	vector<Item> st;
	st.reserve(2*N);
	st.push_back({0, -1, 0, 0});
	while (!st.empty()) {
		auto &it = st.back();
		int u = it.u, p = it.p, state = it.state, &i = it.idx;
		if (state == 0) {
			// enter
			parent[u] = p;
			tin[u] = timer++;
			it.state = 1;
			i = 0;
		} else if (i < (int)adj[u].size()) {
			int v = adj[u][i++];
			if (v == p) continue;
			st.push_back({v, u, 0, 0});
		} else {
			// exit
			tout[u] = timer;
			st.pop_back();
		}
	}
}

// calculate sg[u] = totJ*totI - sum_{each comp when u removed} (J_comp * I_comp)
ll calc_sg(int u) {
	ll bad = 0;
	// for each neighbor, compute that component's J,I
	for (int v: adj[u]) {
		ll Jv, Iv;
		if (v == parent[u]) {
			// outside component = all minus subtree of u
			ll subJ = bitJ.range_sum(tin[u], tout[u]-1);
			ll subI = bitI.range_sum(tin[u], tout[u]-1);
			Jv = totJ - subJ;
			Iv = totI - subI;
		} else {
			// child subtree
			Jv = bitJ.range_sum(tin[v], tout[v]-1);
			Iv = bitI.range_sum(tin[v], tout[v]-1);
		}
		bad += Jv * Iv;
	}
	return totJ * totI - bad;
}

void init(int n, vector<int> F_, vector<int> U, vector<int> V, int Q_) {
	N = n;
	Q = Q_;
	F = F_;
	adj.assign(N, {});
	for (int j = 0; j < N-1; j++) {
		adj[U[j]].push_back(V[j]);
		adj[V[j]].push_back(U[j]);
	}
	build_euler();
	bitJ.init(N);
	bitI.init(N);
	// global counts and Fenwick initial update
	totJ = totI = totO = 0;
	for (int i = 0; i < N; i++) {
		if (F[i] == 0) {
			totJ++;
			bitJ.update(tin[i], +1);
		}
		if (F[i] == 2) {
			totI++;
			bitI.update(tin[i], +1);
		}
		if (F[i] == 1) {
			totO++;
		}
	}
	sg.assign(N, 0);
	ans = 0;
	// compute initial sg for omelette nodes
	for (int u = 0; u < N; u++) {
		if (F[u] == 1) {
			sg[u] = calc_sg(u);
			ans += sg[u];
		}
	}
}

void change(int X, int Y) {
	// if X was omelette, remove its contribution
	if (F[X] == 1) {
		ans -= sg[X];
	}
	// remove old type from counts & Fenwick
	if (F[X] == 0) {
		totJ--;
		bitJ.update(tin[X], -1);
	}
	if (F[X] == 2) {
		totI--;
		bitI.update(tin[X], -1);
	}
	if (F[X] == 1) {
		totO--;
	}
	// update type
	F[X] = Y;
	// add new type
	if (F[X] == 0) {
		totJ++;
		bitJ.update(tin[X], +1);
	}
	if (F[X] == 2) {
		totI++;
		bitI.update(tin[X], +1);
	}
	if (F[X] == 1) {
		totO++;
	}
	// recompute sg for X and its neighbors
	vector<int> touch;
	touch.reserve(adj[X].size()+1);
	touch.push_back(X);
	for (int v: adj[X]) touch.push_back(v);
	for (int u: touch) {
		if (F[u] == 1) {
			ll old = sg[u];
			ll now = calc_sg(u);
			sg[u] = now;
			ans += (now - old);
		}
	}
}

ll num_tours() {
	return ans;
}
//void _main();
//int main() {
//	_main();
//	return 0;
//}
//void _main() {
//
//
//
//}

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