oj.uz

답안 #957789

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957789 2024-04-04T10:26:42 Z ono_de206 Vinjete (COI22_vinjete) C++14
69 / 100
 2712 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;
		// 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

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 256592 KB Output is correct
2 Correct 52 ms 258656 KB Output is correct
3 Correct 53 ms 260692 KB Output is correct
4 Correct 53 ms 262740 KB Output is correct
5 Correct 50 ms 260692 KB Output is correct
6 Correct 51 ms 262736 KB Output is correct
7 Correct 52 ms 260424 KB Output is correct
8 Correct 50 ms 260496 KB Output is correct
9 Correct 50 ms 260432 KB Output is correct
10 Correct 50 ms 260612 KB Output is correct
11 Correct 50 ms 260688 KB Output is correct
12 Correct 51 ms 260520 KB Output is correct
13 Correct 57 ms 260632 KB Output is correct
14 Correct 51 ms 262480 KB Output is correct
15 Correct 49 ms 260560 KB Output is correct
16 Correct 50 ms 260432 KB Output is correct
17 Correct 50 ms 260640 KB Output is correct
18 Correct 51 ms 260628 KB Output is correct
19 Correct 50 ms 262484 KB Output is correct
20 Correct 52 ms 260692 KB Output is correct
21 Correct 53 ms 262644 KB Output is correct
22 Correct 51 ms 260432 KB Output is correct
23 Correct 49 ms 260436 KB Output is correct
24 Correct 53 ms 260436 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 256592 KB Output is correct
2 Correct 52 ms 258656 KB Output is correct
3 Correct 53 ms 260692 KB Output is correct
4 Correct 53 ms 262740 KB Output is correct
5 Correct 50 ms 260692 KB Output is correct
6 Correct 51 ms 262736 KB Output is correct
7 Correct 52 ms 260424 KB Output is correct
8 Correct 50 ms 260496 KB Output is correct
9 Correct 50 ms 260432 KB Output is correct
10 Correct 50 ms 260612 KB Output is correct
11 Correct 50 ms 260688 KB Output is correct
12 Correct 51 ms 260520 KB Output is correct
13 Correct 57 ms 260632 KB Output is correct
14 Correct 51 ms 262480 KB Output is correct
15 Correct 49 ms 260560 KB Output is correct
16 Correct 50 ms 260432 KB Output is correct
17 Correct 50 ms 260640 KB Output is correct
18 Correct 51 ms 260628 KB Output is correct
19 Correct 50 ms 262484 KB Output is correct
20 Correct 52 ms 260692 KB Output is correct
21 Correct 53 ms 262644 KB Output is correct
22 Correct 51 ms 260432 KB Output is correct
23 Correct 49 ms 260436 KB Output is correct
24 Correct 53 ms 260436 KB Output is correct
25 Correct 51 ms 260620 KB Output is correct
26 Correct 50 ms 260692 KB Output is correct
27 Correct 51 ms 264788 KB Output is correct
28 Correct 55 ms 260908 KB Output is correct
29 Correct 51 ms 262596 KB Output is correct
30 Correct 56 ms 262740 KB Output is correct
31 Correct 55 ms 260576 KB Output is correct
32 Correct 53 ms 260588 KB Output is correct
33 Correct 51 ms 262740 KB Output is correct
34 Correct 52 ms 258672 KB Output is correct
35 Correct 50 ms 258384 KB Output is correct
36 Correct 51 ms 256596 KB Output is correct
37 Correct 51 ms 258640 KB Output is correct
38 Correct 51 ms 256572 KB Output is correct
39 Correct 51 ms 256592 KB Output is correct
40 Correct 50 ms 256532 KB Output is correct
41 Correct 50 ms 258668 KB Output is correct
42 Correct 50 ms 258640 KB Output is correct
43 Correct 54 ms 260436 KB Output is correct
44 Correct 51 ms 256544 KB Output is correct
45 Correct 52 ms 258524 KB Output is correct
46 Correct 56 ms 258644 KB Output is correct
47 Correct 50 ms 256612 KB Output is correct
48 Correct 53 ms 258456 KB Output is correct
49 Correct 51 ms 258644 KB Output is correct
50 Correct 51 ms 256592 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 256592 KB Output is correct
2 Correct 52 ms 258656 KB Output is correct
3 Correct 53 ms 260692 KB Output is correct
4 Correct 53 ms 262740 KB Output is correct
5 Correct 50 ms 260692 KB Output is correct
6 Correct 51 ms 262736 KB Output is correct
7 Correct 52 ms 260424 KB Output is correct
8 Correct 50 ms 260496 KB Output is correct
9 Correct 50 ms 260432 KB Output is correct
10 Correct 50 ms 260612 KB Output is correct
11 Correct 50 ms 260688 KB Output is correct
12 Correct 51 ms 260520 KB Output is correct
13 Correct 57 ms 260632 KB Output is correct
14 Correct 51 ms 262480 KB Output is correct
15 Correct 49 ms 260560 KB Output is correct
16 Correct 50 ms 260432 KB Output is correct
17 Correct 50 ms 260640 KB Output is correct
18 Correct 51 ms 260628 KB Output is correct
19 Correct 50 ms 262484 KB Output is correct
20 Correct 52 ms 260692 KB Output is correct
21 Correct 53 ms 262644 KB Output is correct
22 Correct 51 ms 260432 KB Output is correct
23 Correct 49 ms 260436 KB Output is correct
24 Correct 53 ms 260436 KB Output is correct
25 Correct 127 ms 269504 KB Output is correct
26 Correct 121 ms 267704 KB Output is correct
27 Correct 153 ms 273096 KB Output is correct
28 Correct 152 ms 274960 KB Output is correct
29 Correct 155 ms 273204 KB Output is correct
30 Correct 145 ms 275180 KB Output is correct
31 Correct 58 ms 258404 KB Output is correct
32 Correct 63 ms 260548 KB Output is correct
33 Correct 58 ms 260256 KB Output is correct
34 Correct 57 ms 258388 KB Output is correct
35 Correct 121 ms 265268 KB Output is correct
36 Correct 123 ms 265408 KB Output is correct
37 Correct 149 ms 272588 KB Output is correct
38 Correct 164 ms 270840 KB Output is correct
39 Correct 145 ms 272572 KB Output is correct
40 Correct 147 ms 272572 KB Output is correct
41 Correct 60 ms 258128 KB Output is correct
42 Correct 58 ms 260180 KB Output is correct
43 Correct 123 ms 264980 KB Output is correct
44 Correct 129 ms 269112 KB Output is correct
45 Correct 145 ms 272348 KB Output is correct
46 Correct 150 ms 272332 KB Output is correct
47 Correct 145 ms 272244 KB Output is correct
48 Correct 143 ms 270344 KB Output is correct
49 Correct 58 ms 258180 KB Output is correct
50 Correct 60 ms 260040 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 256592 KB Output is correct
2 Correct 52 ms 258656 KB Output is correct
3 Correct 53 ms 260692 KB Output is correct
4 Correct 53 ms 262740 KB Output is correct
5 Correct 50 ms 260692 KB Output is correct
6 Correct 51 ms 262736 KB Output is correct
7 Correct 52 ms 260424 KB Output is correct
8 Correct 50 ms 260496 KB Output is correct
9 Correct 50 ms 260432 KB Output is correct
10 Correct 50 ms 260612 KB Output is correct
11 Correct 50 ms 260688 KB Output is correct
12 Correct 51 ms 260520 KB Output is correct
13 Correct 57 ms 260632 KB Output is correct
14 Correct 51 ms 262480 KB Output is correct
15 Correct 49 ms 260560 KB Output is correct
16 Correct 50 ms 260432 KB Output is correct
17 Correct 50 ms 260640 KB Output is correct
18 Correct 51 ms 260628 KB Output is correct
19 Correct 50 ms 262484 KB Output is correct
20 Correct 52 ms 260692 KB Output is correct
21 Correct 53 ms 262644 KB Output is correct
22 Correct 51 ms 260432 KB Output is correct
23 Correct 49 ms 260436 KB Output is correct
24 Correct 53 ms 260436 KB Output is correct
25 Correct 127 ms 269504 KB Output is correct
26 Correct 121 ms 267704 KB Output is correct
27 Correct 153 ms 273096 KB Output is correct
28 Correct 152 ms 274960 KB Output is correct
29 Correct 155 ms 273204 KB Output is correct
30 Correct 145 ms 275180 KB Output is correct
31 Correct 58 ms 258404 KB Output is correct
32 Correct 63 ms 260548 KB Output is correct
33 Correct 58 ms 260256 KB Output is correct
34 Correct 57 ms 258388 KB Output is correct
35 Correct 121 ms 265268 KB Output is correct
36 Correct 123 ms 265408 KB Output is correct
37 Correct 149 ms 272588 KB Output is correct
38 Correct 164 ms 270840 KB Output is correct
39 Correct 145 ms 272572 KB Output is correct
40 Correct 147 ms 272572 KB Output is correct
41 Correct 60 ms 258128 KB Output is correct
42 Correct 58 ms 260180 KB Output is correct
43 Correct 123 ms 264980 KB Output is correct
44 Correct 129 ms 269112 KB Output is correct
45 Correct 145 ms 272348 KB Output is correct
46 Correct 150 ms 272332 KB Output is correct
47 Correct 145 ms 272244 KB Output is correct
48 Correct 143 ms 270344 KB Output is correct
49 Correct 58 ms 258180 KB Output is correct
50 Correct 60 ms 260040 KB Output is correct
51 Correct 228 ms 284888 KB Output is correct
52 Correct 231 ms 286632 KB Output is correct
53 Correct 340 ms 300156 KB Output is correct
54 Correct 339 ms 302272 KB Output is correct
55 Correct 317 ms 302256 KB Output is correct
56 Correct 313 ms 302508 KB Output is correct
57 Correct 91 ms 265316 KB Output is correct
58 Correct 88 ms 266964 KB Output is correct
59 Correct 95 ms 267128 KB Output is correct
60 Correct 88 ms 267032 KB Output is correct
61 Correct 241 ms 280628 KB Output is correct
62 Correct 244 ms 280980 KB Output is correct
63 Correct 328 ms 295856 KB Output is correct
64 Correct 332 ms 296104 KB Output is correct
65 Correct 308 ms 294440 KB Output is correct
66 Correct 318 ms 296172 KB Output is correct
67 Correct 90 ms 265764 KB Output is correct
68 Correct 90 ms 263872 KB Output is correct
69 Correct 244 ms 277976 KB Output is correct
70 Correct 245 ms 281892 KB Output is correct
71 Correct 336 ms 295408 KB Output is correct
72 Correct 338 ms 295596 KB Output is correct
73 Correct 305 ms 295432 KB Output is correct
74 Correct 310 ms 295780 KB Output is correct
75 Correct 94 ms 265720 KB Output is correct
76 Correct 100 ms 265680 KB Output is correct

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 256592 KB Output is correct
2 Correct 52 ms 258656 KB Output is correct
3 Correct 53 ms 260692 KB Output is correct
4 Correct 53 ms 262740 KB Output is correct
5 Correct 50 ms 260692 KB Output is correct
6 Correct 51 ms 262736 KB Output is correct
7 Correct 52 ms 260424 KB Output is correct
8 Correct 50 ms 260496 KB Output is correct
9 Correct 50 ms 260432 KB Output is correct
10 Correct 50 ms 260612 KB Output is correct
11 Correct 50 ms 260688 KB Output is correct
12 Correct 51 ms 260520 KB Output is correct
13 Correct 57 ms 260632 KB Output is correct
14 Correct 51 ms 262480 KB Output is correct
15 Correct 49 ms 260560 KB Output is correct
16 Correct 50 ms 260432 KB Output is correct
17 Correct 50 ms 260640 KB Output is correct
18 Correct 51 ms 260628 KB Output is correct
19 Correct 50 ms 262484 KB Output is correct
20 Correct 52 ms 260692 KB Output is correct
21 Correct 53 ms 262644 KB Output is correct
22 Correct 51 ms 260432 KB Output is correct
23 Correct 49 ms 260436 KB Output is correct
24 Correct 53 ms 260436 KB Output is correct
25 Correct 51 ms 260620 KB Output is correct
26 Correct 50 ms 260692 KB Output is correct
27 Correct 51 ms 264788 KB Output is correct
28 Correct 55 ms 260908 KB Output is correct
29 Correct 51 ms 262596 KB Output is correct
30 Correct 56 ms 262740 KB Output is correct
31 Correct 55 ms 260576 KB Output is correct
32 Correct 53 ms 260588 KB Output is correct
33 Correct 51 ms 262740 KB Output is correct
34 Correct 52 ms 258672 KB Output is correct
35 Correct 50 ms 258384 KB Output is correct
36 Correct 51 ms 256596 KB Output is correct
37 Correct 51 ms 258640 KB Output is correct
38 Correct 51 ms 256572 KB Output is correct
39 Correct 51 ms 256592 KB Output is correct
40 Correct 50 ms 256532 KB Output is correct
41 Correct 50 ms 258668 KB Output is correct
42 Correct 50 ms 258640 KB Output is correct
43 Correct 54 ms 260436 KB Output is correct
44 Correct 51 ms 256544 KB Output is correct
45 Correct 52 ms 258524 KB Output is correct
46 Correct 56 ms 258644 KB Output is correct
47 Correct 50 ms 256612 KB Output is correct
48 Correct 53 ms 258456 KB Output is correct
49 Correct 51 ms 258644 KB Output is correct
50 Correct 51 ms 256592 KB Output is correct
51 Correct 127 ms 269504 KB Output is correct
52 Correct 121 ms 267704 KB Output is correct
53 Correct 153 ms 273096 KB Output is correct
54 Correct 152 ms 274960 KB Output is correct
55 Correct 155 ms 273204 KB Output is correct
56 Correct 145 ms 275180 KB Output is correct
57 Correct 58 ms 258404 KB Output is correct
58 Correct 63 ms 260548 KB Output is correct
59 Correct 58 ms 260256 KB Output is correct
60 Correct 57 ms 258388 KB Output is correct
61 Correct 121 ms 265268 KB Output is correct
62 Correct 123 ms 265408 KB Output is correct
63 Correct 149 ms 272588 KB Output is correct
64 Correct 164 ms 270840 KB Output is correct
65 Correct 145 ms 272572 KB Output is correct
66 Correct 147 ms 272572 KB Output is correct
67 Correct 60 ms 258128 KB Output is correct
68 Correct 58 ms 260180 KB Output is correct
69 Correct 123 ms 264980 KB Output is correct
70 Correct 129 ms 269112 KB Output is correct
71 Correct 145 ms 272348 KB Output is correct
72 Correct 150 ms 272332 KB Output is correct
73 Correct 145 ms 272244 KB Output is correct
74 Correct 143 ms 270344 KB Output is correct
75 Correct 58 ms 258180 KB Output is correct
76 Correct 60 ms 260040 KB Output is correct
77 Correct 228 ms 284888 KB Output is correct
78 Correct 231 ms 286632 KB Output is correct
79 Correct 340 ms 300156 KB Output is correct
80 Correct 339 ms 302272 KB Output is correct
81 Correct 317 ms 302256 KB Output is correct
82 Correct 313 ms 302508 KB Output is correct
83 Correct 91 ms 265316 KB Output is correct
84 Correct 88 ms 266964 KB Output is correct
85 Correct 95 ms 267128 KB Output is correct
86 Correct 88 ms 267032 KB Output is correct
87 Correct 241 ms 280628 KB Output is correct
88 Correct 244 ms 280980 KB Output is correct
89 Correct 328 ms 295856 KB Output is correct
90 Correct 332 ms 296104 KB Output is correct
91 Correct 308 ms 294440 KB Output is correct
92 Correct 318 ms 296172 KB Output is correct
93 Correct 90 ms 265764 KB Output is correct
94 Correct 90 ms 263872 KB Output is correct
95 Correct 244 ms 277976 KB Output is correct
96 Correct 245 ms 281892 KB Output is correct
97 Correct 336 ms 295408 KB Output is correct
98 Correct 338 ms 295596 KB Output is correct
99 Correct 305 ms 295432 KB Output is correct
100 Correct 310 ms 295780 KB Output is correct
101 Correct 94 ms 265720 KB Output is correct
102 Correct 100 ms 265680 KB Output is correct
103 Correct 233 ms 289184 KB Output is correct
104 Correct 236 ms 289196 KB Output is correct
105 Runtime error 2712 ms 524288 KB Execution killed with signal 9
106 Halted 0 ms 0 KB -