Submission #957786

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
957786	2024-04-04T10:24:56 Z	ono_de206	Vinjete (COI22_vinjete)	C++14	69 / 100	360 ms	522172 KB

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], root[mxn], ans[mxn], lch[mxn * 210], rch[mxn * 210];

struct node {
	int mn, cnt, sum;
	node(int _mn = 0, int _cnt = 0, int _sum = 0) : mn(_mn), cnt(_cnt), sum(_sum) {}
} d[mxn * 210];

node operator+(const node &a, const node &b) {
	node ret;
	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;
		// cout << ll << ' ' << rr << " ----> ";
		ll = lower_bound(all(inters), make_pair(ll, 0)) - inters.begin() + 1;
		rr = lower_bound(all(inters), make_pair(rr, mod)) - inters.begin();
		// cout << ll << ' ' << rr << " here\n";
		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.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	254800 KB	Output is correct
2	Correct	52 ms	255028 KB	Output is correct
3	Correct	51 ms	254804 KB	Output is correct
4	Correct	55 ms	254916 KB	Output is correct
5	Correct	51 ms	254800 KB	Output is correct
6	Correct	50 ms	255056 KB	Output is correct
7	Correct	48 ms	254804 KB	Output is correct
8	Correct	48 ms	254852 KB	Output is correct
9	Correct	52 ms	254800 KB	Output is correct
10	Correct	52 ms	254844 KB	Output is correct
11	Correct	52 ms	254800 KB	Output is correct
12	Correct	51 ms	254804 KB	Output is correct
13	Correct	56 ms	254804 KB	Output is correct
14	Correct	52 ms	254804 KB	Output is correct
15	Correct	50 ms	254800 KB	Output is correct
16	Correct	51 ms	254864 KB	Output is correct
17	Correct	51 ms	254756 KB	Output is correct
18	Correct	50 ms	254752 KB	Output is correct
19	Correct	50 ms	254916 KB	Output is correct
20	Correct	53 ms	254804 KB	Output is correct
21	Correct	50 ms	254860 KB	Output is correct
22	Correct	50 ms	254800 KB	Output is correct
23	Correct	51 ms	254880 KB	Output is correct
24	Correct	48 ms	254796 KB	Output is correct

Subtask #2
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	254800 KB	Output is correct
2	Correct	52 ms	255028 KB	Output is correct
3	Correct	51 ms	254804 KB	Output is correct
4	Correct	55 ms	254916 KB	Output is correct
5	Correct	51 ms	254800 KB	Output is correct
6	Correct	50 ms	255056 KB	Output is correct
7	Correct	48 ms	254804 KB	Output is correct
8	Correct	48 ms	254852 KB	Output is correct
9	Correct	52 ms	254800 KB	Output is correct
10	Correct	52 ms	254844 KB	Output is correct
11	Correct	52 ms	254800 KB	Output is correct
12	Correct	51 ms	254804 KB	Output is correct
13	Correct	56 ms	254804 KB	Output is correct
14	Correct	52 ms	254804 KB	Output is correct
15	Correct	50 ms	254800 KB	Output is correct
16	Correct	51 ms	254864 KB	Output is correct
17	Correct	51 ms	254756 KB	Output is correct
18	Correct	50 ms	254752 KB	Output is correct
19	Correct	50 ms	254916 KB	Output is correct
20	Correct	53 ms	254804 KB	Output is correct
21	Correct	50 ms	254860 KB	Output is correct
22	Correct	50 ms	254800 KB	Output is correct
23	Correct	51 ms	254880 KB	Output is correct
24	Correct	48 ms	254796 KB	Output is correct
25	Correct	50 ms	254804 KB	Output is correct
26	Correct	54 ms	254832 KB	Output is correct
27	Correct	50 ms	255060 KB	Output is correct
28	Correct	57 ms	255060 KB	Output is correct
29	Correct	52 ms	254996 KB	Output is correct
30	Correct	50 ms	255060 KB	Output is correct
31	Correct	51 ms	255060 KB	Output is correct
32	Correct	49 ms	254824 KB	Output is correct
33	Correct	49 ms	255056 KB	Output is correct
34	Correct	51 ms	254916 KB	Output is correct
35	Correct	54 ms	254860 KB	Output is correct
36	Correct	51 ms	254804 KB	Output is correct
37	Correct	51 ms	255312 KB	Output is correct
38	Correct	50 ms	254992 KB	Output is correct
39	Correct	49 ms	254804 KB	Output is correct
40	Correct	51 ms	254796 KB	Output is correct
41	Correct	50 ms	254800 KB	Output is correct
42	Correct	49 ms	254988 KB	Output is correct
43	Correct	50 ms	254976 KB	Output is correct
44	Correct	56 ms	254804 KB	Output is correct
45	Correct	49 ms	254884 KB	Output is correct
46	Correct	49 ms	254800 KB	Output is correct
47	Correct	50 ms	254804 KB	Output is correct
48	Correct	53 ms	254816 KB	Output is correct
49	Correct	49 ms	254828 KB	Output is correct
50	Correct	50 ms	254800 KB	Output is correct

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	254800 KB	Output is correct
2	Correct	52 ms	255028 KB	Output is correct
3	Correct	51 ms	254804 KB	Output is correct
4	Correct	55 ms	254916 KB	Output is correct
5	Correct	51 ms	254800 KB	Output is correct
6	Correct	50 ms	255056 KB	Output is correct
7	Correct	48 ms	254804 KB	Output is correct
8	Correct	48 ms	254852 KB	Output is correct
9	Correct	52 ms	254800 KB	Output is correct
10	Correct	52 ms	254844 KB	Output is correct
11	Correct	52 ms	254800 KB	Output is correct
12	Correct	51 ms	254804 KB	Output is correct
13	Correct	56 ms	254804 KB	Output is correct
14	Correct	52 ms	254804 KB	Output is correct
15	Correct	50 ms	254800 KB	Output is correct
16	Correct	51 ms	254864 KB	Output is correct
17	Correct	51 ms	254756 KB	Output is correct
18	Correct	50 ms	254752 KB	Output is correct
19	Correct	50 ms	254916 KB	Output is correct
20	Correct	53 ms	254804 KB	Output is correct
21	Correct	50 ms	254860 KB	Output is correct
22	Correct	50 ms	254800 KB	Output is correct
23	Correct	51 ms	254880 KB	Output is correct
24	Correct	48 ms	254796 KB	Output is correct
25	Correct	121 ms	264676 KB	Output is correct
26	Correct	118 ms	264788 KB	Output is correct
27	Correct	149 ms	269244 KB	Output is correct
28	Correct	144 ms	269244 KB	Output is correct
29	Correct	144 ms	269184 KB	Output is correct
30	Correct	148 ms	269500 KB	Output is correct
31	Correct	58 ms	255568 KB	Output is correct
32	Correct	60 ms	255572 KB	Output is correct
33	Correct	57 ms	255572 KB	Output is correct
34	Correct	56 ms	255572 KB	Output is correct
35	Correct	120 ms	262228 KB	Output is correct
36	Correct	126 ms	262532 KB	Output is correct
37	Correct	146 ms	266872 KB	Output is correct
38	Correct	145 ms	266736 KB	Output is correct
39	Correct	148 ms	267088 KB	Output is correct
40	Correct	141 ms	266676 KB	Output is correct
41	Correct	57 ms	255360 KB	Output is correct
42	Correct	58 ms	255468 KB	Output is correct
43	Correct	143 ms	262332 KB	Output is correct
44	Correct	120 ms	262072 KB	Output is correct
45	Correct	144 ms	266392 KB	Output is correct
46	Correct	147 ms	266328 KB	Output is correct
47	Correct	149 ms	266580 KB	Output is correct
48	Correct	153 ms	266384 KB	Output is correct
49	Correct	56 ms	255248 KB	Output is correct
50	Correct	58 ms	255324 KB	Output is correct

Subtask #4
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	254800 KB	Output is correct
2	Correct	52 ms	255028 KB	Output is correct
3	Correct	51 ms	254804 KB	Output is correct
4	Correct	55 ms	254916 KB	Output is correct
5	Correct	51 ms	254800 KB	Output is correct
6	Correct	50 ms	255056 KB	Output is correct
7	Correct	48 ms	254804 KB	Output is correct
8	Correct	48 ms	254852 KB	Output is correct
9	Correct	52 ms	254800 KB	Output is correct
10	Correct	52 ms	254844 KB	Output is correct
11	Correct	52 ms	254800 KB	Output is correct
12	Correct	51 ms	254804 KB	Output is correct
13	Correct	56 ms	254804 KB	Output is correct
14	Correct	52 ms	254804 KB	Output is correct
15	Correct	50 ms	254800 KB	Output is correct
16	Correct	51 ms	254864 KB	Output is correct
17	Correct	51 ms	254756 KB	Output is correct
18	Correct	50 ms	254752 KB	Output is correct
19	Correct	50 ms	254916 KB	Output is correct
20	Correct	53 ms	254804 KB	Output is correct
21	Correct	50 ms	254860 KB	Output is correct
22	Correct	50 ms	254800 KB	Output is correct
23	Correct	51 ms	254880 KB	Output is correct
24	Correct	48 ms	254796 KB	Output is correct
25	Correct	121 ms	264676 KB	Output is correct
26	Correct	118 ms	264788 KB	Output is correct
27	Correct	149 ms	269244 KB	Output is correct
28	Correct	144 ms	269244 KB	Output is correct
29	Correct	144 ms	269184 KB	Output is correct
30	Correct	148 ms	269500 KB	Output is correct
31	Correct	58 ms	255568 KB	Output is correct
32	Correct	60 ms	255572 KB	Output is correct
33	Correct	57 ms	255572 KB	Output is correct
34	Correct	56 ms	255572 KB	Output is correct
35	Correct	120 ms	262228 KB	Output is correct
36	Correct	126 ms	262532 KB	Output is correct
37	Correct	146 ms	266872 KB	Output is correct
38	Correct	145 ms	266736 KB	Output is correct
39	Correct	148 ms	267088 KB	Output is correct
40	Correct	141 ms	266676 KB	Output is correct
41	Correct	57 ms	255360 KB	Output is correct
42	Correct	58 ms	255468 KB	Output is correct
43	Correct	143 ms	262332 KB	Output is correct
44	Correct	120 ms	262072 KB	Output is correct
45	Correct	144 ms	266392 KB	Output is correct
46	Correct	147 ms	266328 KB	Output is correct
47	Correct	149 ms	266580 KB	Output is correct
48	Correct	153 ms	266384 KB	Output is correct
49	Correct	56 ms	255248 KB	Output is correct
50	Correct	58 ms	255324 KB	Output is correct
51	Correct	255 ms	281996 KB	Output is correct
52	Correct	224 ms	281992 KB	Output is correct
53	Correct	334 ms	295004 KB	Output is correct
54	Correct	330 ms	295348 KB	Output is correct
55	Correct	357 ms	295280 KB	Output is correct
56	Correct	306 ms	295340 KB	Output is correct
57	Correct	86 ms	262092 KB	Output is correct
58	Correct	86 ms	262340 KB	Output is correct
59	Correct	87 ms	262128 KB	Output is correct
60	Correct	89 ms	262088 KB	Output is correct
61	Correct	236 ms	275900 KB	Output is correct
62	Correct	244 ms	276180 KB	Output is correct
63	Correct	324 ms	288944 KB	Output is correct
64	Correct	354 ms	289144 KB	Output is correct
65	Correct	318 ms	289396 KB	Output is correct
66	Correct	315 ms	289196 KB	Output is correct
67	Correct	89 ms	260936 KB	Output is correct
68	Correct	86 ms	260816 KB	Output is correct
69	Correct	256 ms	275116 KB	Output is correct
70	Correct	281 ms	275112 KB	Output is correct
71	Correct	327 ms	288208 KB	Output is correct
72	Correct	314 ms	288300 KB	Output is correct
73	Correct	300 ms	288220 KB	Output is correct
74	Correct	323 ms	288184 KB	Output is correct
75	Correct	87 ms	260804 KB	Output is correct
76	Correct	88 ms	260808 KB	Output is correct

Subtask #5
0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	254800 KB	Output is correct
2	Correct	52 ms	255028 KB	Output is correct
3	Correct	51 ms	254804 KB	Output is correct
4	Correct	55 ms	254916 KB	Output is correct
5	Correct	51 ms	254800 KB	Output is correct
6	Correct	50 ms	255056 KB	Output is correct
7	Correct	48 ms	254804 KB	Output is correct
8	Correct	48 ms	254852 KB	Output is correct
9	Correct	52 ms	254800 KB	Output is correct
10	Correct	52 ms	254844 KB	Output is correct
11	Correct	52 ms	254800 KB	Output is correct
12	Correct	51 ms	254804 KB	Output is correct
13	Correct	56 ms	254804 KB	Output is correct
14	Correct	52 ms	254804 KB	Output is correct
15	Correct	50 ms	254800 KB	Output is correct
16	Correct	51 ms	254864 KB	Output is correct
17	Correct	51 ms	254756 KB	Output is correct
18	Correct	50 ms	254752 KB	Output is correct
19	Correct	50 ms	254916 KB	Output is correct
20	Correct	53 ms	254804 KB	Output is correct
21	Correct	50 ms	254860 KB	Output is correct
22	Correct	50 ms	254800 KB	Output is correct
23	Correct	51 ms	254880 KB	Output is correct
24	Correct	48 ms	254796 KB	Output is correct
25	Correct	50 ms	254804 KB	Output is correct
26	Correct	54 ms	254832 KB	Output is correct
27	Correct	50 ms	255060 KB	Output is correct
28	Correct	57 ms	255060 KB	Output is correct
29	Correct	52 ms	254996 KB	Output is correct
30	Correct	50 ms	255060 KB	Output is correct
31	Correct	51 ms	255060 KB	Output is correct
32	Correct	49 ms	254824 KB	Output is correct
33	Correct	49 ms	255056 KB	Output is correct
34	Correct	51 ms	254916 KB	Output is correct
35	Correct	54 ms	254860 KB	Output is correct
36	Correct	51 ms	254804 KB	Output is correct
37	Correct	51 ms	255312 KB	Output is correct
38	Correct	50 ms	254992 KB	Output is correct
39	Correct	49 ms	254804 KB	Output is correct
40	Correct	51 ms	254796 KB	Output is correct
41	Correct	50 ms	254800 KB	Output is correct
42	Correct	49 ms	254988 KB	Output is correct
43	Correct	50 ms	254976 KB	Output is correct
44	Correct	56 ms	254804 KB	Output is correct
45	Correct	49 ms	254884 KB	Output is correct
46	Correct	49 ms	254800 KB	Output is correct
47	Correct	50 ms	254804 KB	Output is correct
48	Correct	53 ms	254816 KB	Output is correct
49	Correct	49 ms	254828 KB	Output is correct
50	Correct	50 ms	254800 KB	Output is correct
51	Correct	121 ms	264676 KB	Output is correct
52	Correct	118 ms	264788 KB	Output is correct
53	Correct	149 ms	269244 KB	Output is correct
54	Correct	144 ms	269244 KB	Output is correct
55	Correct	144 ms	269184 KB	Output is correct
56	Correct	148 ms	269500 KB	Output is correct
57	Correct	58 ms	255568 KB	Output is correct
58	Correct	60 ms	255572 KB	Output is correct
59	Correct	57 ms	255572 KB	Output is correct
60	Correct	56 ms	255572 KB	Output is correct
61	Correct	120 ms	262228 KB	Output is correct
62	Correct	126 ms	262532 KB	Output is correct
63	Correct	146 ms	266872 KB	Output is correct
64	Correct	145 ms	266736 KB	Output is correct
65	Correct	148 ms	267088 KB	Output is correct
66	Correct	141 ms	266676 KB	Output is correct
67	Correct	57 ms	255360 KB	Output is correct
68	Correct	58 ms	255468 KB	Output is correct
69	Correct	143 ms	262332 KB	Output is correct
70	Correct	120 ms	262072 KB	Output is correct
71	Correct	144 ms	266392 KB	Output is correct
72	Correct	147 ms	266328 KB	Output is correct
73	Correct	149 ms	266580 KB	Output is correct
74	Correct	153 ms	266384 KB	Output is correct
75	Correct	56 ms	255248 KB	Output is correct
76	Correct	58 ms	255324 KB	Output is correct
77	Correct	255 ms	281996 KB	Output is correct
78	Correct	224 ms	281992 KB	Output is correct
79	Correct	334 ms	295004 KB	Output is correct
80	Correct	330 ms	295348 KB	Output is correct
81	Correct	357 ms	295280 KB	Output is correct
82	Correct	306 ms	295340 KB	Output is correct
83	Correct	86 ms	262092 KB	Output is correct
84	Correct	86 ms	262340 KB	Output is correct
85	Correct	87 ms	262128 KB	Output is correct
86	Correct	89 ms	262088 KB	Output is correct
87	Correct	236 ms	275900 KB	Output is correct
88	Correct	244 ms	276180 KB	Output is correct
89	Correct	324 ms	288944 KB	Output is correct
90	Correct	354 ms	289144 KB	Output is correct
91	Correct	318 ms	289396 KB	Output is correct
92	Correct	315 ms	289196 KB	Output is correct
93	Correct	89 ms	260936 KB	Output is correct
94	Correct	86 ms	260816 KB	Output is correct
95	Correct	256 ms	275116 KB	Output is correct
96	Correct	281 ms	275112 KB	Output is correct
97	Correct	327 ms	288208 KB	Output is correct
98	Correct	314 ms	288300 KB	Output is correct
99	Correct	300 ms	288220 KB	Output is correct
100	Correct	323 ms	288184 KB	Output is correct
101	Correct	87 ms	260804 KB	Output is correct
102	Correct	88 ms	260808 KB	Output is correct
103	Correct	239 ms	282476 KB	Output is correct
104	Correct	250 ms	282284 KB	Output is correct
105	Runtime error	360 ms	522172 KB	Execution killed with signal 11
106	Halted	0 ms	0 KB	-

Submission #957786

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 13.0 / 13.0

Subtask #3 16.0 / 16.0

Subtask #4 29.0 / 29.0

Subtask #5 0 / 31.0

Subtask #1
11.0 / 11.0

Subtask #2
13.0 / 13.0

Subtask #3
16.0 / 16.0

Subtask #4
29.0 / 29.0

Subtask #5
0 / 31.0