Submission #919445

#	Time	Username	Problem	Language	Result	Execution time	Memory
919445		NK_	Vinjete (COI22_vinjete)	C++17	100 / 100	426 ms	232016 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second
#define mp make_pair
#define nl '\n'
#define pb push_back

template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;

const int INF = 1 << 30;

struct node {
	node* c[2]; int L, R, ans, T;

	node(int l, int r): L(l), R(r) { ans = 0, T = INF; c[0] = c[1] = NULL; };

	void pull() {
		if (T != INF) ans = R - L + 1;
		else ans = (c[0] ? c[0]->ans : 0) + (c[1] ? c[1]->ans : 0);
	}

	void upd(int l, int r, int t) {
		// cout << L << " " << R << " " << T << " " << ans << endl;
		if (r < L || R < l || T < t) return;
		if (l <= L && R <= r) {
			if (t > 0) T = t;
			else {
				if (T == -t) T = INF;
				else return;
			}
			pull();
			// cout << "UPD: " << L << " " << R << " " << T << " " << ans << endl;
			return;
		}


		int M = (L + R) / 2;

		if (!c[0]) c[0] = new node(L, M);
		if (!c[1]) c[1] = new node(M + 1, R);

		c[0]->upd(l, r, t);
		c[1]->upd(l, r, t);

		pull();
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	node* st = new node(0, INF - 1);

	int N, M; cin >> N >> M;

	V<vpi> adj(N); vi L(N - 1), R(N - 1);

	for(int i = 0; i < N - 1; i++) {
		int u, v, l, r; cin >> u >> v >> l >> r; --u, --v, --l, --r;
		adj[u].pb(mp(v, i));
		adj[v].pb(mp(u, i));
		L[i] = l, R[i] = r;
	}

	int t = 1;
	vi ans(N);
	function<void(int, int)> dfs = [&](int u, int p) {
		ans[u] = st->ans;

		t++;
		for(auto& e : adj[u]) if (e.f != p) {
			int v, i; tie(v, i) = e;

			int cur = t;
			st->upd(L[i], R[i], cur);
			dfs(v, u);
			st->upd(L[i], R[i], -cur);
		}
	};

	dfs(0, -1);

	for(int i = 1; i < N; i++) cout << ans[i] << nl;

	exit(0-0);
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31