Submission #957794

#	Time	Username	Problem	Language	Result	Execution time	Memory
957794		ono_de206	Vinjete (COI22_vinjete)	C++14	100 / 100	332 ms	110884 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long

typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
// typedef pair<int, int> P;

template<typename T, typename U>
ostream & operator << (ostream &out, const pair<T, U> &c) {
	out << c.first << ' ' << c.second;
	return out;
}

template<typename T>
ostream & operator << (ostream &out, vector<T> &v) {
	const int sz = v.size();
	for (int i = 0; i < sz; i++) {
		if (i) out << ' ';
		out << v[i];
	}
	return out;
}

template<typename T>
istream & operator >> (istream &in, vector<T> &v) {
	for (T &x : v) in >> x;
	return in;
}

template<typename T, typename U>
	istream & operator >> (istream &in, pair<T, U> &c) {
	in >> c.first;
	in >> c.second;
	return in;
}

template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

const int mxn = 1e5 + 10, MXLOG = 22, mod = 1e9 + 7, P = 1181, D = 1523;//, N = 2500;
const long long inf = 2e18 + 10;
vector<tuple<int, int, int>> g[mxn];
int N, T, n, m, sg[mxn * 2], root[mxn], ans[mxn], lch[mxn * 300], rch[mxn * 300];

struct node {
	int mn, cnt, sum;
} d[mxn * 300];

node operator+(const node &a, const node &b) {
	node ret{0, 0, 0};
	ret.mn = min(a.mn, b.mn + a.sum);
	ret.sum = a.sum + b.sum;
	if(ret.mn == a.mn) ret.cnt += a.cnt;
	if(ret.mn == b.mn + a.sum) ret.cnt += b.cnt;
	return ret;
}

int build(int l, int r) {
	int save = ++T;
	if(l < r) {
		int m = (l + r) / 2;
		lch[save] = build(l, m);
		rch[save] = build(m + 1, r);
		d[save] = d[lch[save]] + d[rch[save]];
	} else {
		d[save].cnt = sg[l];
	}
	return save;
}

int update(int l, int r, int i, int x, int y) {
	int save = ++T;
	if(l == r) {
		d[save] = d[i];
		d[save].mn += y;
		d[save].sum += y;
		return save;
	}
	int m = (l + r) / 2;
	if(x <= m) {
		lch[save] = update(l, m, lch[i], x, y);
		rch[save] = rch[i];
	} else {
		lch[save] = lch[i];
		rch[save] = update(m + 1, r, rch[i], x, y);
	}
	d[save] = d[lch[save]] + d[rch[save]];
	return save;
}

void dfs(int to, int fr) {
	for(auto it : g[to]) {
		int x, ll, rr;
		tie(x, ll, rr) = it;
		if(x == fr) continue;
		root[x] = update(1, N, root[to], ll, 1);
		if(rr + 1 <= N) root[x] = update(1, N, root[x], rr + 1, -1);
		if(d[root[x]].mn != 0) ans[x] = m;
		else ans[x] = m - d[root[x]].cnt;
		dfs(x, to);
	}
}

void go() {
	cin >> n >> m;
	vector<tuple<int, int, int, int>> edges;
	vector<pair<int, int>> v, inters;
	v.eb(1, 0);
	v.eb(m, 1);
	for(int i = 1; i < n; i++) {
		int x, y, ll, rr;
		cin >> x >> y >> ll >> rr;
		edges.eb(x, y, ll, rr);
		v.eb(ll, 0);
		v.eb(rr, 1);
	}
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	int ls = 1;
	for(auto it : v) {
		int l = ls, r = (it.ss == 0 ? it.ff - 1 : it.ff);
		if(l <= r) inters.eb(l, r);
		ls = r + 1;
	}
	N = inters.size();
	for(int i = 1; i <= N; i++) {
		sg[i] = inters[i - 1].ss - inters[i - 1].ff + 1;
	}
	for(auto it : edges) {
		int x, y, ll, rr;
		tie(x, y, ll, rr) = it;
		ll = lower_bound(all(inters), make_pair(ll, 0)) - inters.begin() + 1;
		rr = lower_bound(all(inters), make_pair(rr, mod)) - inters.begin();
		g[x].eb(y, ll, rr);
		g[y].eb(x, ll, rr);
	}
	root[1] = build(1, N);
	dfs(1, 0);
	for(int i = 2; i <= n; i++) {
		cout << ans[i] << endl;
	}
}

signed main() {
	fast;
	int t = 1;
	// cin >> t;
	while(t--) {
		go();
	}
	return 0;
}

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