Submission #957795

# Submission time Handle Problem Language Result Execution time Memory
957795 2024-04-04T10:39:34 Z ono_de206 Vinjete (COI22_vinjete) C++14
100 / 100
349 ms 108844 KB
#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 * 200], rch[mxn * 200];

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

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;
}
# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 4 ms 12196 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 4 ms 12124 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 4 ms 12124 KB Output is correct
12 Correct 4 ms 12124 KB Output is correct
13 Correct 5 ms 12124 KB Output is correct
14 Correct 4 ms 12124 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 4 ms 12124 KB Output is correct
18 Correct 4 ms 12124 KB Output is correct
19 Correct 4 ms 12124 KB Output is correct
20 Correct 4 ms 12376 KB Output is correct
21 Correct 4 ms 12124 KB Output is correct
22 Correct 4 ms 12124 KB Output is correct
23 Correct 2 ms 9820 KB Output is correct
24 Correct 2 ms 9820 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 4 ms 12196 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 4 ms 12124 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 4 ms 12124 KB Output is correct
12 Correct 4 ms 12124 KB Output is correct
13 Correct 5 ms 12124 KB Output is correct
14 Correct 4 ms 12124 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 4 ms 12124 KB Output is correct
18 Correct 4 ms 12124 KB Output is correct
19 Correct 4 ms 12124 KB Output is correct
20 Correct 4 ms 12376 KB Output is correct
21 Correct 4 ms 12124 KB Output is correct
22 Correct 4 ms 12124 KB Output is correct
23 Correct 2 ms 9820 KB Output is correct
24 Correct 2 ms 9820 KB Output is correct
25 Correct 4 ms 12124 KB Output is correct
26 Correct 4 ms 12124 KB Output is correct
27 Correct 4 ms 12124 KB Output is correct
28 Correct 4 ms 12124 KB Output is correct
29 Correct 4 ms 12124 KB Output is correct
30 Correct 4 ms 12376 KB Output is correct
31 Correct 4 ms 12120 KB Output is correct
32 Correct 4 ms 12240 KB Output is correct
33 Correct 4 ms 12124 KB Output is correct
34 Correct 4 ms 12124 KB Output is correct
35 Correct 4 ms 12160 KB Output is correct
36 Correct 4 ms 12124 KB Output is correct
37 Correct 6 ms 12124 KB Output is correct
38 Correct 4 ms 12124 KB Output is correct
39 Correct 4 ms 12120 KB Output is correct
40 Correct 4 ms 12124 KB Output is correct
41 Correct 4 ms 12124 KB Output is correct
42 Correct 4 ms 12324 KB Output is correct
43 Correct 4 ms 12124 KB Output is correct
44 Correct 5 ms 12124 KB Output is correct
45 Correct 5 ms 12124 KB Output is correct
46 Correct 4 ms 12124 KB Output is correct
47 Correct 4 ms 12120 KB Output is correct
48 Correct 4 ms 12124 KB Output is correct
49 Correct 5 ms 12376 KB Output is correct
50 Correct 4 ms 12124 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 4 ms 12196 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 4 ms 12124 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 4 ms 12124 KB Output is correct
12 Correct 4 ms 12124 KB Output is correct
13 Correct 5 ms 12124 KB Output is correct
14 Correct 4 ms 12124 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 4 ms 12124 KB Output is correct
18 Correct 4 ms 12124 KB Output is correct
19 Correct 4 ms 12124 KB Output is correct
20 Correct 4 ms 12376 KB Output is correct
21 Correct 4 ms 12124 KB Output is correct
22 Correct 4 ms 12124 KB Output is correct
23 Correct 2 ms 9820 KB Output is correct
24 Correct 2 ms 9820 KB Output is correct
25 Correct 74 ms 28068 KB Output is correct
26 Correct 76 ms 28148 KB Output is correct
27 Correct 100 ms 42684 KB Output is correct
28 Correct 101 ms 42680 KB Output is correct
29 Correct 110 ms 42612 KB Output is correct
30 Correct 107 ms 42864 KB Output is correct
31 Correct 11 ms 12892 KB Output is correct
32 Correct 12 ms 12892 KB Output is correct
33 Correct 12 ms 12888 KB Output is correct
34 Correct 11 ms 12892 KB Output is correct
35 Correct 76 ms 25532 KB Output is correct
36 Correct 77 ms 25740 KB Output is correct
37 Correct 100 ms 40128 KB Output is correct
38 Correct 101 ms 40532 KB Output is correct
39 Correct 96 ms 40384 KB Output is correct
40 Correct 100 ms 40276 KB Output is correct
41 Correct 11 ms 12636 KB Output is correct
42 Correct 11 ms 12636 KB Output is correct
43 Correct 77 ms 25324 KB Output is correct
44 Correct 77 ms 25276 KB Output is correct
45 Correct 99 ms 40132 KB Output is correct
46 Correct 105 ms 40112 KB Output is correct
47 Correct 97 ms 39984 KB Output is correct
48 Correct 95 ms 39916 KB Output is correct
49 Correct 11 ms 12380 KB Output is correct
50 Correct 11 ms 12380 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 4 ms 12196 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 4 ms 12124 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 4 ms 12124 KB Output is correct
12 Correct 4 ms 12124 KB Output is correct
13 Correct 5 ms 12124 KB Output is correct
14 Correct 4 ms 12124 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 4 ms 12124 KB Output is correct
18 Correct 4 ms 12124 KB Output is correct
19 Correct 4 ms 12124 KB Output is correct
20 Correct 4 ms 12376 KB Output is correct
21 Correct 4 ms 12124 KB Output is correct
22 Correct 4 ms 12124 KB Output is correct
23 Correct 2 ms 9820 KB Output is correct
24 Correct 2 ms 9820 KB Output is correct
25 Correct 74 ms 28068 KB Output is correct
26 Correct 76 ms 28148 KB Output is correct
27 Correct 100 ms 42684 KB Output is correct
28 Correct 101 ms 42680 KB Output is correct
29 Correct 110 ms 42612 KB Output is correct
30 Correct 107 ms 42864 KB Output is correct
31 Correct 11 ms 12892 KB Output is correct
32 Correct 12 ms 12892 KB Output is correct
33 Correct 12 ms 12888 KB Output is correct
34 Correct 11 ms 12892 KB Output is correct
35 Correct 76 ms 25532 KB Output is correct
36 Correct 77 ms 25740 KB Output is correct
37 Correct 100 ms 40128 KB Output is correct
38 Correct 101 ms 40532 KB Output is correct
39 Correct 96 ms 40384 KB Output is correct
40 Correct 100 ms 40276 KB Output is correct
41 Correct 11 ms 12636 KB Output is correct
42 Correct 11 ms 12636 KB Output is correct
43 Correct 77 ms 25324 KB Output is correct
44 Correct 77 ms 25276 KB Output is correct
45 Correct 99 ms 40132 KB Output is correct
46 Correct 105 ms 40112 KB Output is correct
47 Correct 97 ms 39984 KB Output is correct
48 Correct 95 ms 39916 KB Output is correct
49 Correct 11 ms 12380 KB Output is correct
50 Correct 11 ms 12380 KB Output is correct
51 Correct 189 ms 58012 KB Output is correct
52 Correct 187 ms 57512 KB Output is correct
53 Correct 287 ms 97200 KB Output is correct
54 Correct 292 ms 97492 KB Output is correct
55 Correct 270 ms 97032 KB Output is correct
56 Correct 277 ms 97084 KB Output is correct
57 Correct 41 ms 25296 KB Output is correct
58 Correct 41 ms 25288 KB Output is correct
59 Correct 40 ms 25292 KB Output is correct
60 Correct 40 ms 25516 KB Output is correct
61 Correct 196 ms 51624 KB Output is correct
62 Correct 194 ms 51576 KB Output is correct
63 Correct 283 ms 90916 KB Output is correct
64 Correct 282 ms 90996 KB Output is correct
65 Correct 279 ms 91212 KB Output is correct
66 Correct 261 ms 90792 KB Output is correct
67 Correct 42 ms 24124 KB Output is correct
68 Correct 47 ms 24016 KB Output is correct
69 Correct 214 ms 50888 KB Output is correct
70 Correct 206 ms 50584 KB Output is correct
71 Correct 264 ms 90228 KB Output is correct
72 Correct 271 ms 90680 KB Output is correct
73 Correct 256 ms 90156 KB Output is correct
74 Correct 252 ms 90028 KB Output is correct
75 Correct 42 ms 24116 KB Output is correct
76 Correct 43 ms 24092 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 12120 KB Output is correct
2 Correct 4 ms 12196 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 4 ms 12124 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 4 ms 12124 KB Output is correct
12 Correct 4 ms 12124 KB Output is correct
13 Correct 5 ms 12124 KB Output is correct
14 Correct 4 ms 12124 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 4 ms 12124 KB Output is correct
18 Correct 4 ms 12124 KB Output is correct
19 Correct 4 ms 12124 KB Output is correct
20 Correct 4 ms 12376 KB Output is correct
21 Correct 4 ms 12124 KB Output is correct
22 Correct 4 ms 12124 KB Output is correct
23 Correct 2 ms 9820 KB Output is correct
24 Correct 2 ms 9820 KB Output is correct
25 Correct 4 ms 12124 KB Output is correct
26 Correct 4 ms 12124 KB Output is correct
27 Correct 4 ms 12124 KB Output is correct
28 Correct 4 ms 12124 KB Output is correct
29 Correct 4 ms 12124 KB Output is correct
30 Correct 4 ms 12376 KB Output is correct
31 Correct 4 ms 12120 KB Output is correct
32 Correct 4 ms 12240 KB Output is correct
33 Correct 4 ms 12124 KB Output is correct
34 Correct 4 ms 12124 KB Output is correct
35 Correct 4 ms 12160 KB Output is correct
36 Correct 4 ms 12124 KB Output is correct
37 Correct 6 ms 12124 KB Output is correct
38 Correct 4 ms 12124 KB Output is correct
39 Correct 4 ms 12120 KB Output is correct
40 Correct 4 ms 12124 KB Output is correct
41 Correct 4 ms 12124 KB Output is correct
42 Correct 4 ms 12324 KB Output is correct
43 Correct 4 ms 12124 KB Output is correct
44 Correct 5 ms 12124 KB Output is correct
45 Correct 5 ms 12124 KB Output is correct
46 Correct 4 ms 12124 KB Output is correct
47 Correct 4 ms 12120 KB Output is correct
48 Correct 4 ms 12124 KB Output is correct
49 Correct 5 ms 12376 KB Output is correct
50 Correct 4 ms 12124 KB Output is correct
51 Correct 74 ms 28068 KB Output is correct
52 Correct 76 ms 28148 KB Output is correct
53 Correct 100 ms 42684 KB Output is correct
54 Correct 101 ms 42680 KB Output is correct
55 Correct 110 ms 42612 KB Output is correct
56 Correct 107 ms 42864 KB Output is correct
57 Correct 11 ms 12892 KB Output is correct
58 Correct 12 ms 12892 KB Output is correct
59 Correct 12 ms 12888 KB Output is correct
60 Correct 11 ms 12892 KB Output is correct
61 Correct 76 ms 25532 KB Output is correct
62 Correct 77 ms 25740 KB Output is correct
63 Correct 100 ms 40128 KB Output is correct
64 Correct 101 ms 40532 KB Output is correct
65 Correct 96 ms 40384 KB Output is correct
66 Correct 100 ms 40276 KB Output is correct
67 Correct 11 ms 12636 KB Output is correct
68 Correct 11 ms 12636 KB Output is correct
69 Correct 77 ms 25324 KB Output is correct
70 Correct 77 ms 25276 KB Output is correct
71 Correct 99 ms 40132 KB Output is correct
72 Correct 105 ms 40112 KB Output is correct
73 Correct 97 ms 39984 KB Output is correct
74 Correct 95 ms 39916 KB Output is correct
75 Correct 11 ms 12380 KB Output is correct
76 Correct 11 ms 12380 KB Output is correct
77 Correct 189 ms 58012 KB Output is correct
78 Correct 187 ms 57512 KB Output is correct
79 Correct 287 ms 97200 KB Output is correct
80 Correct 292 ms 97492 KB Output is correct
81 Correct 270 ms 97032 KB Output is correct
82 Correct 277 ms 97084 KB Output is correct
83 Correct 41 ms 25296 KB Output is correct
84 Correct 41 ms 25288 KB Output is correct
85 Correct 40 ms 25292 KB Output is correct
86 Correct 40 ms 25516 KB Output is correct
87 Correct 196 ms 51624 KB Output is correct
88 Correct 194 ms 51576 KB Output is correct
89 Correct 283 ms 90916 KB Output is correct
90 Correct 282 ms 90996 KB Output is correct
91 Correct 279 ms 91212 KB Output is correct
92 Correct 261 ms 90792 KB Output is correct
93 Correct 42 ms 24124 KB Output is correct
94 Correct 47 ms 24016 KB Output is correct
95 Correct 214 ms 50888 KB Output is correct
96 Correct 206 ms 50584 KB Output is correct
97 Correct 264 ms 90228 KB Output is correct
98 Correct 271 ms 90680 KB Output is correct
99 Correct 256 ms 90156 KB Output is correct
100 Correct 252 ms 90028 KB Output is correct
101 Correct 42 ms 24116 KB Output is correct
102 Correct 43 ms 24092 KB Output is correct
103 Correct 202 ms 57896 KB Output is correct
104 Correct 189 ms 57980 KB Output is correct
105 Correct 324 ms 108664 KB Output is correct
106 Correct 349 ms 108844 KB Output is correct
107 Correct 286 ms 108160 KB Output is correct
108 Correct 313 ms 108332 KB Output is correct
109 Correct 42 ms 27716 KB Output is correct
110 Correct 43 ms 27716 KB Output is correct
111 Correct 42 ms 27484 KB Output is correct
112 Correct 42 ms 27472 KB Output is correct
113 Correct 196 ms 52272 KB Output is correct
114 Correct 200 ms 52040 KB Output is correct
115 Correct 320 ms 102828 KB Output is correct
116 Correct 333 ms 102932 KB Output is correct
117 Correct 285 ms 102248 KB Output is correct
118 Correct 300 ms 101960 KB Output is correct
119 Correct 43 ms 26636 KB Output is correct
120 Correct 45 ms 26396 KB Output is correct
121 Correct 200 ms 51000 KB Output is correct
122 Correct 206 ms 51112 KB Output is correct
123 Correct 299 ms 101908 KB Output is correct
124 Correct 313 ms 101908 KB Output is correct
125 Correct 284 ms 101164 KB Output is correct
126 Correct 300 ms 101444 KB Output is correct
127 Correct 44 ms 26192 KB Output is correct
128 Correct 46 ms 26188 KB Output is correct