oj.uz

Submission #957782

# Submission time Handle Problem Language Result Execution time Memory
957782 2024-04-04T10:19:36 Z ono_de206 Vinjete (COI22_vinjete) C++14
69 / 100
 2576 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 * 220], rch[mxn * 220];

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

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 139 ms 261964 KB Output is correct
2 Correct 68 ms 261920 KB Output is correct
3 Correct 68 ms 261972 KB Output is correct
4 Correct 67 ms 261972 KB Output is correct
5 Correct 72 ms 261968 KB Output is correct
6 Correct 64 ms 261968 KB Output is correct
7 Correct 70 ms 261732 KB Output is correct
8 Correct 67 ms 261788 KB Output is correct
9 Correct 67 ms 261920 KB Output is correct
10 Correct 66 ms 261972 KB Output is correct
11 Correct 66 ms 261964 KB Output is correct
12 Correct 68 ms 266220 KB Output is correct
13 Correct 59 ms 261952 KB Output is correct
14 Correct 53 ms 261984 KB Output is correct
15 Correct 52 ms 261716 KB Output is correct
16 Correct 52 ms 261776 KB Output is correct
17 Correct 53 ms 261972 KB Output is correct
18 Correct 55 ms 261972 KB Output is correct
19 Correct 51 ms 261968 KB Output is correct
20 Correct 53 ms 261968 KB Output is correct
21 Correct 51 ms 261968 KB Output is correct
22 Correct 56 ms 262016 KB Output is correct
23 Correct 51 ms 261752 KB Output is correct
24 Correct 54 ms 261840 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 261964 KB Output is correct
2 Correct 68 ms 261920 KB Output is correct
3 Correct 68 ms 261972 KB Output is correct
4 Correct 67 ms 261972 KB Output is correct
5 Correct 72 ms 261968 KB Output is correct
6 Correct 64 ms 261968 KB Output is correct
7 Correct 70 ms 261732 KB Output is correct
8 Correct 67 ms 261788 KB Output is correct
9 Correct 67 ms 261920 KB Output is correct
10 Correct 66 ms 261972 KB Output is correct
11 Correct 66 ms 261964 KB Output is correct
12 Correct 68 ms 266220 KB Output is correct
13 Correct 59 ms 261952 KB Output is correct
14 Correct 53 ms 261984 KB Output is correct
15 Correct 52 ms 261716 KB Output is correct
16 Correct 52 ms 261776 KB Output is correct
17 Correct 53 ms 261972 KB Output is correct
18 Correct 55 ms 261972 KB Output is correct
19 Correct 51 ms 261968 KB Output is correct
20 Correct 53 ms 261968 KB Output is correct
21 Correct 51 ms 261968 KB Output is correct
22 Correct 56 ms 262016 KB Output is correct
23 Correct 51 ms 261752 KB Output is correct
24 Correct 54 ms 261840 KB Output is correct
25 Correct 53 ms 261972 KB Output is correct
26 Correct 52 ms 261968 KB Output is correct
27 Correct 54 ms 261988 KB Output is correct
28 Correct 52 ms 261964 KB Output is correct
29 Correct 53 ms 261968 KB Output is correct
30 Correct 52 ms 261996 KB Output is correct
31 Correct 52 ms 262132 KB Output is correct
32 Correct 60 ms 261972 KB Output is correct
33 Correct 53 ms 262224 KB Output is correct
34 Correct 54 ms 262372 KB Output is correct
35 Correct 51 ms 262480 KB Output is correct
36 Correct 53 ms 261848 KB Output is correct
37 Correct 52 ms 262244 KB Output is correct
38 Correct 52 ms 262228 KB Output is correct
39 Correct 53 ms 261972 KB Output is correct
40 Correct 60 ms 261952 KB Output is correct
41 Correct 53 ms 261972 KB Output is correct
42 Correct 53 ms 262084 KB Output is correct
43 Correct 53 ms 261968 KB Output is correct
44 Correct 55 ms 262384 KB Output is correct
45 Correct 53 ms 261972 KB Output is correct
46 Correct 52 ms 262220 KB Output is correct
47 Correct 51 ms 262228 KB Output is correct
48 Correct 52 ms 262228 KB Output is correct
49 Correct 53 ms 261992 KB Output is correct
50 Correct 54 ms 262228 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 261964 KB Output is correct
2 Correct 68 ms 261920 KB Output is correct
3 Correct 68 ms 261972 KB Output is correct
4 Correct 67 ms 261972 KB Output is correct
5 Correct 72 ms 261968 KB Output is correct
6 Correct 64 ms 261968 KB Output is correct
7 Correct 70 ms 261732 KB Output is correct
8 Correct 67 ms 261788 KB Output is correct
9 Correct 67 ms 261920 KB Output is correct
10 Correct 66 ms 261972 KB Output is correct
11 Correct 66 ms 261964 KB Output is correct
12 Correct 68 ms 266220 KB Output is correct
13 Correct 59 ms 261952 KB Output is correct
14 Correct 53 ms 261984 KB Output is correct
15 Correct 52 ms 261716 KB Output is correct
16 Correct 52 ms 261776 KB Output is correct
17 Correct 53 ms 261972 KB Output is correct
18 Correct 55 ms 261972 KB Output is correct
19 Correct 51 ms 261968 KB Output is correct
20 Correct 53 ms 261968 KB Output is correct
21 Correct 51 ms 261968 KB Output is correct
22 Correct 56 ms 262016 KB Output is correct
23 Correct 51 ms 261752 KB Output is correct
24 Correct 54 ms 261840 KB Output is correct
25 Correct 124 ms 274104 KB Output is correct
26 Correct 121 ms 274068 KB Output is correct
27 Correct 157 ms 279672 KB Output is correct
28 Correct 148 ms 279488 KB Output is correct
29 Correct 148 ms 279612 KB Output is correct
30 Correct 147 ms 279996 KB Output is correct
31 Correct 60 ms 264040 KB Output is correct
32 Correct 60 ms 264016 KB Output is correct
33 Correct 60 ms 264020 KB Output is correct
34 Correct 60 ms 264020 KB Output is correct
35 Correct 134 ms 272060 KB Output is correct
36 Correct 127 ms 271744 KB Output is correct
37 Correct 153 ms 277180 KB Output is correct
38 Correct 151 ms 277260 KB Output is correct
39 Correct 149 ms 277152 KB Output is correct
40 Correct 148 ms 277176 KB Output is correct
41 Correct 58 ms 263516 KB Output is correct
42 Correct 61 ms 263564 KB Output is correct
43 Correct 128 ms 271748 KB Output is correct
44 Correct 125 ms 271548 KB Output is correct
45 Correct 150 ms 276928 KB Output is correct
46 Correct 146 ms 276924 KB Output is correct
47 Correct 160 ms 276924 KB Output is correct
48 Correct 146 ms 276924 KB Output is correct
49 Correct 62 ms 263508 KB Output is correct
50 Correct 61 ms 263516 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 261964 KB Output is correct
2 Correct 68 ms 261920 KB Output is correct
3 Correct 68 ms 261972 KB Output is correct
4 Correct 67 ms 261972 KB Output is correct
5 Correct 72 ms 261968 KB Output is correct
6 Correct 64 ms 261968 KB Output is correct
7 Correct 70 ms 261732 KB Output is correct
8 Correct 67 ms 261788 KB Output is correct
9 Correct 67 ms 261920 KB Output is correct
10 Correct 66 ms 261972 KB Output is correct
11 Correct 66 ms 261964 KB Output is correct
12 Correct 68 ms 266220 KB Output is correct
13 Correct 59 ms 261952 KB Output is correct
14 Correct 53 ms 261984 KB Output is correct
15 Correct 52 ms 261716 KB Output is correct
16 Correct 52 ms 261776 KB Output is correct
17 Correct 53 ms 261972 KB Output is correct
18 Correct 55 ms 261972 KB Output is correct
19 Correct 51 ms 261968 KB Output is correct
20 Correct 53 ms 261968 KB Output is correct
21 Correct 51 ms 261968 KB Output is correct
22 Correct 56 ms 262016 KB Output is correct
23 Correct 51 ms 261752 KB Output is correct
24 Correct 54 ms 261840 KB Output is correct
25 Correct 124 ms 274104 KB Output is correct
26 Correct 121 ms 274068 KB Output is correct
27 Correct 157 ms 279672 KB Output is correct
28 Correct 148 ms 279488 KB Output is correct
29 Correct 148 ms 279612 KB Output is correct
30 Correct 147 ms 279996 KB Output is correct
31 Correct 60 ms 264040 KB Output is correct
32 Correct 60 ms 264016 KB Output is correct
33 Correct 60 ms 264020 KB Output is correct
34 Correct 60 ms 264020 KB Output is correct
35 Correct 134 ms 272060 KB Output is correct
36 Correct 127 ms 271744 KB Output is correct
37 Correct 153 ms 277180 KB Output is correct
38 Correct 151 ms 277260 KB Output is correct
39 Correct 149 ms 277152 KB Output is correct
40 Correct 148 ms 277176 KB Output is correct
41 Correct 58 ms 263516 KB Output is correct
42 Correct 61 ms 263564 KB Output is correct
43 Correct 128 ms 271748 KB Output is correct
44 Correct 125 ms 271548 KB Output is correct
45 Correct 150 ms 276928 KB Output is correct
46 Correct 146 ms 276924 KB Output is correct
47 Correct 160 ms 276924 KB Output is correct
48 Correct 146 ms 276924 KB Output is correct
49 Correct 62 ms 263508 KB Output is correct
50 Correct 61 ms 263516 KB Output is correct
51 Correct 235 ms 292644 KB Output is correct
52 Correct 258 ms 292608 KB Output is correct
53 Correct 347 ms 308412 KB Output is correct
54 Correct 333 ms 308448 KB Output is correct
55 Correct 326 ms 308580 KB Output is correct
56 Correct 328 ms 308688 KB Output is correct
57 Correct 91 ms 270980 KB Output is correct
58 Correct 92 ms 271044 KB Output is correct
59 Correct 90 ms 270980 KB Output is correct
60 Correct 91 ms 271028 KB Output is correct
61 Correct 249 ms 286520 KB Output is correct
62 Correct 247 ms 286864 KB Output is correct
63 Correct 325 ms 302260 KB Output is correct
64 Correct 341 ms 302400 KB Output is correct
65 Correct 311 ms 302768 KB Output is correct
66 Correct 313 ms 302608 KB Output is correct
67 Correct 102 ms 269764 KB Output is correct
68 Correct 93 ms 269768 KB Output is correct
69 Correct 249 ms 285760 KB Output is correct
70 Correct 245 ms 285868 KB Output is correct
71 Correct 333 ms 301896 KB Output is correct
72 Correct 329 ms 301968 KB Output is correct
73 Correct 329 ms 301540 KB Output is correct
74 Correct 313 ms 301532 KB Output is correct
75 Correct 95 ms 269676 KB Output is correct
76 Correct 94 ms 269904 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 261964 KB Output is correct
2 Correct 68 ms 261920 KB Output is correct
3 Correct 68 ms 261972 KB Output is correct
4 Correct 67 ms 261972 KB Output is correct
5 Correct 72 ms 261968 KB Output is correct
6 Correct 64 ms 261968 KB Output is correct
7 Correct 70 ms 261732 KB Output is correct
8 Correct 67 ms 261788 KB Output is correct
9 Correct 67 ms 261920 KB Output is correct
10 Correct 66 ms 261972 KB Output is correct
11 Correct 66 ms 261964 KB Output is correct
12 Correct 68 ms 266220 KB Output is correct
13 Correct 59 ms 261952 KB Output is correct
14 Correct 53 ms 261984 KB Output is correct
15 Correct 52 ms 261716 KB Output is correct
16 Correct 52 ms 261776 KB Output is correct
17 Correct 53 ms 261972 KB Output is correct
18 Correct 55 ms 261972 KB Output is correct
19 Correct 51 ms 261968 KB Output is correct
20 Correct 53 ms 261968 KB Output is correct
21 Correct 51 ms 261968 KB Output is correct
22 Correct 56 ms 262016 KB Output is correct
23 Correct 51 ms 261752 KB Output is correct
24 Correct 54 ms 261840 KB Output is correct
25 Correct 53 ms 261972 KB Output is correct
26 Correct 52 ms 261968 KB Output is correct
27 Correct 54 ms 261988 KB Output is correct
28 Correct 52 ms 261964 KB Output is correct
29 Correct 53 ms 261968 KB Output is correct
30 Correct 52 ms 261996 KB Output is correct
31 Correct 52 ms 262132 KB Output is correct
32 Correct 60 ms 261972 KB Output is correct
33 Correct 53 ms 262224 KB Output is correct
34 Correct 54 ms 262372 KB Output is correct
35 Correct 51 ms 262480 KB Output is correct
36 Correct 53 ms 261848 KB Output is correct
37 Correct 52 ms 262244 KB Output is correct
38 Correct 52 ms 262228 KB Output is correct
39 Correct 53 ms 261972 KB Output is correct
40 Correct 60 ms 261952 KB Output is correct
41 Correct 53 ms 261972 KB Output is correct
42 Correct 53 ms 262084 KB Output is correct
43 Correct 53 ms 261968 KB Output is correct
44 Correct 55 ms 262384 KB Output is correct
45 Correct 53 ms 261972 KB Output is correct
46 Correct 52 ms 262220 KB Output is correct
47 Correct 51 ms 262228 KB Output is correct
48 Correct 52 ms 262228 KB Output is correct
49 Correct 53 ms 261992 KB Output is correct
50 Correct 54 ms 262228 KB Output is correct
51 Correct 124 ms 274104 KB Output is correct
52 Correct 121 ms 274068 KB Output is correct
53 Correct 157 ms 279672 KB Output is correct
54 Correct 148 ms 279488 KB Output is correct
55 Correct 148 ms 279612 KB Output is correct
56 Correct 147 ms 279996 KB Output is correct
57 Correct 60 ms 264040 KB Output is correct
58 Correct 60 ms 264016 KB Output is correct
59 Correct 60 ms 264020 KB Output is correct
60 Correct 60 ms 264020 KB Output is correct
61 Correct 134 ms 272060 KB Output is correct
62 Correct 127 ms 271744 KB Output is correct
63 Correct 153 ms 277180 KB Output is correct
64 Correct 151 ms 277260 KB Output is correct
65 Correct 149 ms 277152 KB Output is correct
66 Correct 148 ms 277176 KB Output is correct
67 Correct 58 ms 263516 KB Output is correct
68 Correct 61 ms 263564 KB Output is correct
69 Correct 128 ms 271748 KB Output is correct
70 Correct 125 ms 271548 KB Output is correct
71 Correct 150 ms 276928 KB Output is correct
72 Correct 146 ms 276924 KB Output is correct
73 Correct 160 ms 276924 KB Output is correct
74 Correct 146 ms 276924 KB Output is correct
75 Correct 62 ms 263508 KB Output is correct
76 Correct 61 ms 263516 KB Output is correct
77 Correct 235 ms 292644 KB Output is correct
78 Correct 258 ms 292608 KB Output is correct
79 Correct 347 ms 308412 KB Output is correct
80 Correct 333 ms 308448 KB Output is correct
81 Correct 326 ms 308580 KB Output is correct
82 Correct 328 ms 308688 KB Output is correct
83 Correct 91 ms 270980 KB Output is correct
84 Correct 92 ms 271044 KB Output is correct
85 Correct 90 ms 270980 KB Output is correct
86 Correct 91 ms 271028 KB Output is correct
87 Correct 249 ms 286520 KB Output is correct
88 Correct 247 ms 286864 KB Output is correct
89 Correct 325 ms 302260 KB Output is correct
90 Correct 341 ms 302400 KB Output is correct
91 Correct 311 ms 302768 KB Output is correct
92 Correct 313 ms 302608 KB Output is correct
93 Correct 102 ms 269764 KB Output is correct
94 Correct 93 ms 269768 KB Output is correct
95 Correct 249 ms 285760 KB Output is correct
96 Correct 245 ms 285868 KB Output is correct
97 Correct 333 ms 301896 KB Output is correct
98 Correct 329 ms 301968 KB Output is correct
99 Correct 329 ms 301540 KB Output is correct
100 Correct 313 ms 301532 KB Output is correct
101 Correct 95 ms 269676 KB Output is correct
102 Correct 94 ms 269904 KB Output is correct
103 Correct 238 ms 293544 KB Output is correct
104 Correct 238 ms 293500 KB Output is correct
105 Runtime error 2576 ms 524288 KB Execution killed with signal 9
106 Halted 0 ms 0 KB -