oj.uz

Submission #957791

# Submission time Handle Problem Language Result Execution time Memory
957791 2024-04-04T10:33:10 Z ono_de206 Vinjete (COI22_vinjete) C++14
69 / 100
 2609 ms 524288 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], root[mxn], ans[mxn], lch[mxn * 215], rch[mxn * 215];

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

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;
		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);
	}
	if(N > mxn * 2 + 1) exit(1);
	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 152 ms 256596 KB Output is correct
2 Correct 52 ms 256612 KB Output is correct
3 Correct 54 ms 256588 KB Output is correct
4 Correct 50 ms 256596 KB Output is correct
5 Correct 52 ms 256600 KB Output is correct
6 Correct 51 ms 256640 KB Output is correct
7 Correct 48 ms 256244 KB Output is correct
8 Correct 49 ms 256336 KB Output is correct
9 Correct 51 ms 256524 KB Output is correct
10 Correct 52 ms 256376 KB Output is correct
11 Correct 53 ms 256596 KB Output is correct
12 Correct 55 ms 256468 KB Output is correct
13 Correct 51 ms 256596 KB Output is correct
14 Correct 50 ms 256592 KB Output is correct
15 Correct 49 ms 256336 KB Output is correct
16 Correct 50 ms 256340 KB Output is correct
17 Correct 50 ms 256592 KB Output is correct
18 Correct 50 ms 256528 KB Output is correct
19 Correct 53 ms 256596 KB Output is correct
20 Correct 52 ms 256648 KB Output is correct
21 Correct 53 ms 256596 KB Output is correct
22 Correct 54 ms 256660 KB Output is correct
23 Correct 49 ms 256336 KB Output is correct
24 Correct 51 ms 256340 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 256596 KB Output is correct
2 Correct 52 ms 256612 KB Output is correct
3 Correct 54 ms 256588 KB Output is correct
4 Correct 50 ms 256596 KB Output is correct
5 Correct 52 ms 256600 KB Output is correct
6 Correct 51 ms 256640 KB Output is correct
7 Correct 48 ms 256244 KB Output is correct
8 Correct 49 ms 256336 KB Output is correct
9 Correct 51 ms 256524 KB Output is correct
10 Correct 52 ms 256376 KB Output is correct
11 Correct 53 ms 256596 KB Output is correct
12 Correct 55 ms 256468 KB Output is correct
13 Correct 51 ms 256596 KB Output is correct
14 Correct 50 ms 256592 KB Output is correct
15 Correct 49 ms 256336 KB Output is correct
16 Correct 50 ms 256340 KB Output is correct
17 Correct 50 ms 256592 KB Output is correct
18 Correct 50 ms 256528 KB Output is correct
19 Correct 53 ms 256596 KB Output is correct
20 Correct 52 ms 256648 KB Output is correct
21 Correct 53 ms 256596 KB Output is correct
22 Correct 54 ms 256660 KB Output is correct
23 Correct 49 ms 256336 KB Output is correct
24 Correct 51 ms 256340 KB Output is correct
25 Correct 51 ms 256592 KB Output is correct
26 Correct 51 ms 256560 KB Output is correct
27 Correct 53 ms 256592 KB Output is correct
28 Correct 53 ms 256776 KB Output is correct
29 Correct 53 ms 256736 KB Output is correct
30 Correct 52 ms 257008 KB Output is correct
31 Correct 53 ms 256596 KB Output is correct
32 Correct 52 ms 256780 KB Output is correct
33 Correct 53 ms 256676 KB Output is correct
34 Correct 52 ms 256536 KB Output is correct
35 Correct 52 ms 256848 KB Output is correct
36 Correct 52 ms 256632 KB Output is correct
37 Correct 52 ms 256664 KB Output is correct
38 Correct 55 ms 256596 KB Output is correct
39 Correct 51 ms 256592 KB Output is correct
40 Correct 51 ms 256728 KB Output is correct
41 Correct 51 ms 256596 KB Output is correct
42 Correct 51 ms 256644 KB Output is correct
43 Correct 51 ms 256408 KB Output is correct
44 Correct 52 ms 256576 KB Output is correct
45 Correct 51 ms 256592 KB Output is correct
46 Correct 51 ms 256724 KB Output is correct
47 Correct 52 ms 256548 KB Output is correct
48 Correct 50 ms 256592 KB Output is correct
49 Correct 55 ms 256716 KB Output is correct
50 Correct 51 ms 256596 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 256596 KB Output is correct
2 Correct 52 ms 256612 KB Output is correct
3 Correct 54 ms 256588 KB Output is correct
4 Correct 50 ms 256596 KB Output is correct
5 Correct 52 ms 256600 KB Output is correct
6 Correct 51 ms 256640 KB Output is correct
7 Correct 48 ms 256244 KB Output is correct
8 Correct 49 ms 256336 KB Output is correct
9 Correct 51 ms 256524 KB Output is correct
10 Correct 52 ms 256376 KB Output is correct
11 Correct 53 ms 256596 KB Output is correct
12 Correct 55 ms 256468 KB Output is correct
13 Correct 51 ms 256596 KB Output is correct
14 Correct 50 ms 256592 KB Output is correct
15 Correct 49 ms 256336 KB Output is correct
16 Correct 50 ms 256340 KB Output is correct
17 Correct 50 ms 256592 KB Output is correct
18 Correct 50 ms 256528 KB Output is correct
19 Correct 53 ms 256596 KB Output is correct
20 Correct 52 ms 256648 KB Output is correct
21 Correct 53 ms 256596 KB Output is correct
22 Correct 54 ms 256660 KB Output is correct
23 Correct 49 ms 256336 KB Output is correct
24 Correct 51 ms 256340 KB Output is correct
25 Correct 129 ms 267700 KB Output is correct
26 Correct 124 ms 267596 KB Output is correct
27 Correct 149 ms 272928 KB Output is correct
28 Correct 151 ms 272976 KB Output is correct
29 Correct 146 ms 273164 KB Output is correct
30 Correct 147 ms 273088 KB Output is correct
31 Correct 60 ms 258288 KB Output is correct
32 Correct 59 ms 258388 KB Output is correct
33 Correct 59 ms 258384 KB Output is correct
34 Correct 60 ms 258392 KB Output is correct
35 Correct 124 ms 265096 KB Output is correct
36 Correct 129 ms 265652 KB Output is correct
37 Correct 148 ms 270456 KB Output is correct
38 Correct 148 ms 270796 KB Output is correct
39 Correct 150 ms 270708 KB Output is correct
40 Correct 147 ms 270524 KB Output is correct
41 Correct 59 ms 258204 KB Output is correct
42 Correct 60 ms 258204 KB Output is correct
43 Correct 122 ms 264888 KB Output is correct
44 Correct 123 ms 265028 KB Output is correct
45 Correct 147 ms 270292 KB Output is correct
46 Correct 148 ms 270264 KB Output is correct
47 Correct 149 ms 270680 KB Output is correct
48 Correct 143 ms 270268 KB Output is correct
49 Correct 61 ms 258132 KB Output is correct
50 Correct 59 ms 258064 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 256596 KB Output is correct
2 Correct 52 ms 256612 KB Output is correct
3 Correct 54 ms 256588 KB Output is correct
4 Correct 50 ms 256596 KB Output is correct
5 Correct 52 ms 256600 KB Output is correct
6 Correct 51 ms 256640 KB Output is correct
7 Correct 48 ms 256244 KB Output is correct
8 Correct 49 ms 256336 KB Output is correct
9 Correct 51 ms 256524 KB Output is correct
10 Correct 52 ms 256376 KB Output is correct
11 Correct 53 ms 256596 KB Output is correct
12 Correct 55 ms 256468 KB Output is correct
13 Correct 51 ms 256596 KB Output is correct
14 Correct 50 ms 256592 KB Output is correct
15 Correct 49 ms 256336 KB Output is correct
16 Correct 50 ms 256340 KB Output is correct
17 Correct 50 ms 256592 KB Output is correct
18 Correct 50 ms 256528 KB Output is correct
19 Correct 53 ms 256596 KB Output is correct
20 Correct 52 ms 256648 KB Output is correct
21 Correct 53 ms 256596 KB Output is correct
22 Correct 54 ms 256660 KB Output is correct
23 Correct 49 ms 256336 KB Output is correct
24 Correct 51 ms 256340 KB Output is correct
25 Correct 129 ms 267700 KB Output is correct
26 Correct 124 ms 267596 KB Output is correct
27 Correct 149 ms 272928 KB Output is correct
28 Correct 151 ms 272976 KB Output is correct
29 Correct 146 ms 273164 KB Output is correct
30 Correct 147 ms 273088 KB Output is correct
31 Correct 60 ms 258288 KB Output is correct
32 Correct 59 ms 258388 KB Output is correct
33 Correct 59 ms 258384 KB Output is correct
34 Correct 60 ms 258392 KB Output is correct
35 Correct 124 ms 265096 KB Output is correct
36 Correct 129 ms 265652 KB Output is correct
37 Correct 148 ms 270456 KB Output is correct
38 Correct 148 ms 270796 KB Output is correct
39 Correct 150 ms 270708 KB Output is correct
40 Correct 147 ms 270524 KB Output is correct
41 Correct 59 ms 258204 KB Output is correct
42 Correct 60 ms 258204 KB Output is correct
43 Correct 122 ms 264888 KB Output is correct
44 Correct 123 ms 265028 KB Output is correct
45 Correct 147 ms 270292 KB Output is correct
46 Correct 148 ms 270264 KB Output is correct
47 Correct 149 ms 270680 KB Output is correct
48 Correct 143 ms 270268 KB Output is correct
49 Correct 61 ms 258132 KB Output is correct
50 Correct 59 ms 258064 KB Output is correct
51 Correct 237 ms 285232 KB Output is correct
52 Correct 231 ms 284636 KB Output is correct
53 Correct 326 ms 300208 KB Output is correct
54 Correct 335 ms 300508 KB Output is correct
55 Correct 319 ms 300372 KB Output is correct
56 Correct 345 ms 300384 KB Output is correct
57 Correct 88 ms 265108 KB Output is correct
58 Correct 89 ms 265156 KB Output is correct
59 Correct 88 ms 265156 KB Output is correct
60 Correct 89 ms 264900 KB Output is correct
61 Correct 241 ms 278772 KB Output is correct
62 Correct 242 ms 279092 KB Output is correct
63 Correct 324 ms 293892 KB Output is correct
64 Correct 343 ms 294232 KB Output is correct
65 Correct 314 ms 294560 KB Output is correct
66 Correct 317 ms 294108 KB Output is correct
67 Correct 89 ms 263876 KB Output is correct
68 Correct 91 ms 263880 KB Output is correct
69 Correct 245 ms 277812 KB Output is correct
70 Correct 246 ms 278144 KB Output is correct
71 Correct 317 ms 293440 KB Output is correct
72 Correct 327 ms 293800 KB Output is correct
73 Correct 308 ms 293440 KB Output is correct
74 Correct 309 ms 293460 KB Output is correct
75 Correct 92 ms 265680 KB Output is correct
76 Correct 90 ms 263620 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 256596 KB Output is correct
2 Correct 52 ms 256612 KB Output is correct
3 Correct 54 ms 256588 KB Output is correct
4 Correct 50 ms 256596 KB Output is correct
5 Correct 52 ms 256600 KB Output is correct
6 Correct 51 ms 256640 KB Output is correct
7 Correct 48 ms 256244 KB Output is correct
8 Correct 49 ms 256336 KB Output is correct
9 Correct 51 ms 256524 KB Output is correct
10 Correct 52 ms 256376 KB Output is correct
11 Correct 53 ms 256596 KB Output is correct
12 Correct 55 ms 256468 KB Output is correct
13 Correct 51 ms 256596 KB Output is correct
14 Correct 50 ms 256592 KB Output is correct
15 Correct 49 ms 256336 KB Output is correct
16 Correct 50 ms 256340 KB Output is correct
17 Correct 50 ms 256592 KB Output is correct
18 Correct 50 ms 256528 KB Output is correct
19 Correct 53 ms 256596 KB Output is correct
20 Correct 52 ms 256648 KB Output is correct
21 Correct 53 ms 256596 KB Output is correct
22 Correct 54 ms 256660 KB Output is correct
23 Correct 49 ms 256336 KB Output is correct
24 Correct 51 ms 256340 KB Output is correct
25 Correct 51 ms 256592 KB Output is correct
26 Correct 51 ms 256560 KB Output is correct
27 Correct 53 ms 256592 KB Output is correct
28 Correct 53 ms 256776 KB Output is correct
29 Correct 53 ms 256736 KB Output is correct
30 Correct 52 ms 257008 KB Output is correct
31 Correct 53 ms 256596 KB Output is correct
32 Correct 52 ms 256780 KB Output is correct
33 Correct 53 ms 256676 KB Output is correct
34 Correct 52 ms 256536 KB Output is correct
35 Correct 52 ms 256848 KB Output is correct
36 Correct 52 ms 256632 KB Output is correct
37 Correct 52 ms 256664 KB Output is correct
38 Correct 55 ms 256596 KB Output is correct
39 Correct 51 ms 256592 KB Output is correct
40 Correct 51 ms 256728 KB Output is correct
41 Correct 51 ms 256596 KB Output is correct
42 Correct 51 ms 256644 KB Output is correct
43 Correct 51 ms 256408 KB Output is correct
44 Correct 52 ms 256576 KB Output is correct
45 Correct 51 ms 256592 KB Output is correct
46 Correct 51 ms 256724 KB Output is correct
47 Correct 52 ms 256548 KB Output is correct
48 Correct 50 ms 256592 KB Output is correct
49 Correct 55 ms 256716 KB Output is correct
50 Correct 51 ms 256596 KB Output is correct
51 Correct 129 ms 267700 KB Output is correct
52 Correct 124 ms 267596 KB Output is correct
53 Correct 149 ms 272928 KB Output is correct
54 Correct 151 ms 272976 KB Output is correct
55 Correct 146 ms 273164 KB Output is correct
56 Correct 147 ms 273088 KB Output is correct
57 Correct 60 ms 258288 KB Output is correct
58 Correct 59 ms 258388 KB Output is correct
59 Correct 59 ms 258384 KB Output is correct
60 Correct 60 ms 258392 KB Output is correct
61 Correct 124 ms 265096 KB Output is correct
62 Correct 129 ms 265652 KB Output is correct
63 Correct 148 ms 270456 KB Output is correct
64 Correct 148 ms 270796 KB Output is correct
65 Correct 150 ms 270708 KB Output is correct
66 Correct 147 ms 270524 KB Output is correct
67 Correct 59 ms 258204 KB Output is correct
68 Correct 60 ms 258204 KB Output is correct
69 Correct 122 ms 264888 KB Output is correct
70 Correct 123 ms 265028 KB Output is correct
71 Correct 147 ms 270292 KB Output is correct
72 Correct 148 ms 270264 KB Output is correct
73 Correct 149 ms 270680 KB Output is correct
74 Correct 143 ms 270268 KB Output is correct
75 Correct 61 ms 258132 KB Output is correct
76 Correct 59 ms 258064 KB Output is correct
77 Correct 237 ms 285232 KB Output is correct
78 Correct 231 ms 284636 KB Output is correct
79 Correct 326 ms 300208 KB Output is correct
80 Correct 335 ms 300508 KB Output is correct
81 Correct 319 ms 300372 KB Output is correct
82 Correct 345 ms 300384 KB Output is correct
83 Correct 88 ms 265108 KB Output is correct
84 Correct 89 ms 265156 KB Output is correct
85 Correct 88 ms 265156 KB Output is correct
86 Correct 89 ms 264900 KB Output is correct
87 Correct 241 ms 278772 KB Output is correct
88 Correct 242 ms 279092 KB Output is correct
89 Correct 324 ms 293892 KB Output is correct
90 Correct 343 ms 294232 KB Output is correct
91 Correct 314 ms 294560 KB Output is correct
92 Correct 317 ms 294108 KB Output is correct
93 Correct 89 ms 263876 KB Output is correct
94 Correct 91 ms 263880 KB Output is correct
95 Correct 245 ms 277812 KB Output is correct
96 Correct 246 ms 278144 KB Output is correct
97 Correct 317 ms 293440 KB Output is correct
98 Correct 327 ms 293800 KB Output is correct
99 Correct 308 ms 293440 KB Output is correct
100 Correct 309 ms 293460 KB Output is correct
101 Correct 92 ms 265680 KB Output is correct
102 Correct 90 ms 263620 KB Output is correct
103 Correct 240 ms 287164 KB Output is correct
104 Correct 236 ms 285100 KB Output is correct
105 Runtime error 2609 ms 524288 KB Execution killed with signal 9
106 Halted 0 ms 0 KB -