oj.uz

Submission #761378

# Submission time Handle Problem Language Result Execution time Memory
761378 2023-06-19T14:48:30 Z Dan4Life Vinjete (COI22_vinjete) C++17
100 / 100
 524 ms 520776 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const int mxN = (int)1e5+10;
const int Lg = (int)4e2;
int n, mx, IND = 1;
int seg[mxN*Lg], lzy[mxN*Lg];
vector<array<int,3>> adj[mxN];
int ans[mxN], root[mxN], L[mxN*Lg], R[mxN*Lg];

int newLeaf(int v){ int p = ++IND; seg[p]=v; return p; }

int newParent(int l, int r){
	int p = ++IND; L[p]=l, R[p]=r; lzy[p]=-1;
	seg[p] = seg[L[p]]+seg[R[p]];
	return p;
}

int newlzyChild(int p, int v, int l, int r){
	int ind = ++IND;
	L[ind] = L[p];
	R[ind] = R[p];
	lzy[ind] = v;
	seg[ind] = (r-l+1)*v;
	return ind;
}

void prop(int p, int l, int r){
	if(!p or l==r or lzy[p]==-1) return;
	int mid = (l+r)/2;
	if(!L[p]) L[p]=++IND;
	if(!R[p]) R[p]=++IND;
	L[p] = newlzyChild(L[p],lzy[p],l,mid);
	R[p] = newlzyChild(R[p],lzy[p],mid+1,r);
	lzy[p]=-1;
}

int upd(int i, int j, int v, int p, int l=1, int r=mx){
	if(i>r or j<l or i>j or !p) return p; prop(p,l,r);
	if(i<=l and r<=j) return newlzyChild(p,v,l,r);
	int mid = (l+r)/2;
	if(!L[p] and i<=mid) L[p]=++IND;
	if(!R[p] and j>mid) R[p]=++IND;
	return newParent(upd(i,j,v,L[p],l,mid),upd(i,j,v,R[p],mid+1,r));
}

int query(int i, int j, int p, int l=1, int r=mx){
	if(i>r or j<l or i>j or !p) return 0; prop(p,l,r);
	if(i<=l and r<=j) return seg[p];
	int mid = (l+r)/2;
	return query(i,j,L[p],l,mid)+query(i,j,R[p],mid+1,r);
}

void dfs(int s, int p){
	ans[s] = seg[root[s]];
	for(auto [u,v,w] : adj[s])
		if(u!=p) root[u] = upd(v,w,1,root[s]), dfs(u,s);
}

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> mx; root[1] = 1;
	memset(lzy,-1,sizeof(lzy));
	for(int i = 1; i < n; i++){
		int a, b, l, r; cin >> a >> b >> l >> r;
		adj[a].pb({b,l,r}), adj[b].pb({a,l,r});
	}
	dfs(1,0);
	for(int i = 2; i <= n; i++) cout << ans[i] << "\n";
}

Compilation message

Main.cpp: In function 'int upd(int, int, int, int, int, int)':
Main.cpp:42:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   42 |  if(i>r or j<l or i>j or !p) return p; prop(p,l,r);
      |  ^~
Main.cpp:42:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   42 |  if(i>r or j<l or i>j or !p) return p; prop(p,l,r);
      |                                        ^~~~
Main.cpp: In function 'int query(int, int, int, int, int)':
Main.cpp:51:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   51 |  if(i>r or j<l or i>j or !p) return 0; prop(p,l,r);
      |  ^~
Main.cpp:51:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   51 |  if(i>r or j<l or i>j or !p) return 0; prop(p,l,r);
      |                                        ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 160076 KB Output is correct
2 Correct 56 ms 159996 KB Output is correct
3 Correct 58 ms 159948 KB Output is correct
4 Correct 60 ms 159932 KB Output is correct
5 Correct 58 ms 159436 KB Output is correct
6 Correct 59 ms 159448 KB Output is correct
7 Correct 59 ms 159216 KB Output is correct
8 Correct 62 ms 159288 KB Output is correct
9 Correct 58 ms 159892 KB Output is correct
10 Correct 58 ms 159876 KB Output is correct
11 Correct 59 ms 159920 KB Output is correct
12 Correct 57 ms 159792 KB Output is correct
13 Correct 57 ms 159436 KB Output is correct
14 Correct 57 ms 159384 KB Output is correct
15 Correct 58 ms 159184 KB Output is correct
16 Correct 57 ms 159220 KB Output is correct
17 Correct 59 ms 159872 KB Output is correct
18 Correct 59 ms 159776 KB Output is correct
19 Correct 60 ms 159804 KB Output is correct
20 Correct 59 ms 159808 KB Output is correct
21 Correct 58 ms 159440 KB Output is correct
22 Correct 58 ms 159456 KB Output is correct
23 Correct 57 ms 159224 KB Output is correct
24 Correct 59 ms 159280 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 160076 KB Output is correct
2 Correct 56 ms 159996 KB Output is correct
3 Correct 58 ms 159948 KB Output is correct
4 Correct 60 ms 159932 KB Output is correct
5 Correct 58 ms 159436 KB Output is correct
6 Correct 59 ms 159448 KB Output is correct
7 Correct 59 ms 159216 KB Output is correct
8 Correct 62 ms 159288 KB Output is correct
9 Correct 58 ms 159892 KB Output is correct
10 Correct 58 ms 159876 KB Output is correct
11 Correct 59 ms 159920 KB Output is correct
12 Correct 57 ms 159792 KB Output is correct
13 Correct 57 ms 159436 KB Output is correct
14 Correct 57 ms 159384 KB Output is correct
15 Correct 58 ms 159184 KB Output is correct
16 Correct 57 ms 159220 KB Output is correct
17 Correct 59 ms 159872 KB Output is correct
18 Correct 59 ms 159776 KB Output is correct
19 Correct 60 ms 159804 KB Output is correct
20 Correct 59 ms 159808 KB Output is correct
21 Correct 58 ms 159440 KB Output is correct
22 Correct 58 ms 159456 KB Output is correct
23 Correct 57 ms 159224 KB Output is correct
24 Correct 59 ms 159280 KB Output is correct
25 Correct 61 ms 161900 KB Output is correct
26 Correct 61 ms 161840 KB Output is correct
27 Correct 64 ms 163148 KB Output is correct
28 Correct 62 ms 163148 KB Output is correct
29 Correct 60 ms 159896 KB Output is correct
30 Correct 61 ms 159920 KB Output is correct
31 Correct 62 ms 160736 KB Output is correct
32 Correct 60 ms 160656 KB Output is correct
33 Correct 61 ms 160772 KB Output is correct
34 Correct 60 ms 160696 KB Output is correct
35 Correct 61 ms 161356 KB Output is correct
36 Correct 63 ms 161444 KB Output is correct
37 Correct 62 ms 163116 KB Output is correct
38 Correct 61 ms 163176 KB Output is correct
39 Correct 59 ms 159904 KB Output is correct
40 Correct 61 ms 159844 KB Output is correct
41 Correct 60 ms 160636 KB Output is correct
42 Correct 61 ms 160728 KB Output is correct
43 Correct 60 ms 161200 KB Output is correct
44 Correct 60 ms 161228 KB Output is correct
45 Correct 62 ms 162744 KB Output is correct
46 Correct 62 ms 162888 KB Output is correct
47 Correct 60 ms 159900 KB Output is correct
48 Correct 59 ms 159820 KB Output is correct
49 Correct 61 ms 160704 KB Output is correct
50 Correct 62 ms 160780 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 160076 KB Output is correct
2 Correct 56 ms 159996 KB Output is correct
3 Correct 58 ms 159948 KB Output is correct
4 Correct 60 ms 159932 KB Output is correct
5 Correct 58 ms 159436 KB Output is correct
6 Correct 59 ms 159448 KB Output is correct
7 Correct 59 ms 159216 KB Output is correct
8 Correct 62 ms 159288 KB Output is correct
9 Correct 58 ms 159892 KB Output is correct
10 Correct 58 ms 159876 KB Output is correct
11 Correct 59 ms 159920 KB Output is correct
12 Correct 57 ms 159792 KB Output is correct
13 Correct 57 ms 159436 KB Output is correct
14 Correct 57 ms 159384 KB Output is correct
15 Correct 58 ms 159184 KB Output is correct
16 Correct 57 ms 159220 KB Output is correct
17 Correct 59 ms 159872 KB Output is correct
18 Correct 59 ms 159776 KB Output is correct
19 Correct 60 ms 159804 KB Output is correct
20 Correct 59 ms 159808 KB Output is correct
21 Correct 58 ms 159440 KB Output is correct
22 Correct 58 ms 159456 KB Output is correct
23 Correct 57 ms 159224 KB Output is correct
24 Correct 59 ms 159280 KB Output is correct
25 Correct 118 ms 211892 KB Output is correct
26 Correct 110 ms 211964 KB Output is correct
27 Correct 119 ms 210384 KB Output is correct
28 Correct 121 ms 210212 KB Output is correct
29 Correct 91 ms 172708 KB Output is correct
30 Correct 86 ms 172492 KB Output is correct
31 Correct 62 ms 161332 KB Output is correct
32 Correct 61 ms 161328 KB Output is correct
33 Correct 62 ms 161356 KB Output is correct
34 Correct 62 ms 161252 KB Output is correct
35 Correct 118 ms 202700 KB Output is correct
36 Correct 117 ms 202864 KB Output is correct
37 Correct 120 ms 208588 KB Output is correct
38 Correct 123 ms 208236 KB Output is correct
39 Correct 144 ms 170656 KB Output is correct
40 Correct 87 ms 170580 KB Output is correct
41 Correct 60 ms 161080 KB Output is correct
42 Correct 61 ms 161044 KB Output is correct
43 Correct 112 ms 199372 KB Output is correct
44 Correct 109 ms 199536 KB Output is correct
45 Correct 120 ms 203148 KB Output is correct
46 Correct 122 ms 202200 KB Output is correct
47 Correct 93 ms 169832 KB Output is correct
48 Correct 89 ms 169916 KB Output is correct
49 Correct 66 ms 161488 KB Output is correct
50 Correct 64 ms 161016 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 160076 KB Output is correct
2 Correct 56 ms 159996 KB Output is correct
3 Correct 58 ms 159948 KB Output is correct
4 Correct 60 ms 159932 KB Output is correct
5 Correct 58 ms 159436 KB Output is correct
6 Correct 59 ms 159448 KB Output is correct
7 Correct 59 ms 159216 KB Output is correct
8 Correct 62 ms 159288 KB Output is correct
9 Correct 58 ms 159892 KB Output is correct
10 Correct 58 ms 159876 KB Output is correct
11 Correct 59 ms 159920 KB Output is correct
12 Correct 57 ms 159792 KB Output is correct
13 Correct 57 ms 159436 KB Output is correct
14 Correct 57 ms 159384 KB Output is correct
15 Correct 58 ms 159184 KB Output is correct
16 Correct 57 ms 159220 KB Output is correct
17 Correct 59 ms 159872 KB Output is correct
18 Correct 59 ms 159776 KB Output is correct
19 Correct 60 ms 159804 KB Output is correct
20 Correct 59 ms 159808 KB Output is correct
21 Correct 58 ms 159440 KB Output is correct
22 Correct 58 ms 159456 KB Output is correct
23 Correct 57 ms 159224 KB Output is correct
24 Correct 59 ms 159280 KB Output is correct
25 Correct 118 ms 211892 KB Output is correct
26 Correct 110 ms 211964 KB Output is correct
27 Correct 119 ms 210384 KB Output is correct
28 Correct 121 ms 210212 KB Output is correct
29 Correct 91 ms 172708 KB Output is correct
30 Correct 86 ms 172492 KB Output is correct
31 Correct 62 ms 161332 KB Output is correct
32 Correct 61 ms 161328 KB Output is correct
33 Correct 62 ms 161356 KB Output is correct
34 Correct 62 ms 161252 KB Output is correct
35 Correct 118 ms 202700 KB Output is correct
36 Correct 117 ms 202864 KB Output is correct
37 Correct 120 ms 208588 KB Output is correct
38 Correct 123 ms 208236 KB Output is correct
39 Correct 144 ms 170656 KB Output is correct
40 Correct 87 ms 170580 KB Output is correct
41 Correct 60 ms 161080 KB Output is correct
42 Correct 61 ms 161044 KB Output is correct
43 Correct 112 ms 199372 KB Output is correct
44 Correct 109 ms 199536 KB Output is correct
45 Correct 120 ms 203148 KB Output is correct
46 Correct 122 ms 202200 KB Output is correct
47 Correct 93 ms 169832 KB Output is correct
48 Correct 89 ms 169916 KB Output is correct
49 Correct 66 ms 161488 KB Output is correct
50 Correct 64 ms 161016 KB Output is correct
51 Correct 203 ms 302056 KB Output is correct
52 Correct 194 ms 302012 KB Output is correct
53 Correct 236 ms 300620 KB Output is correct
54 Correct 229 ms 300556 KB Output is correct
55 Correct 143 ms 194112 KB Output is correct
56 Correct 145 ms 194208 KB Output is correct
57 Correct 73 ms 167600 KB Output is correct
58 Correct 73 ms 167496 KB Output is correct
59 Correct 73 ms 167500 KB Output is correct
60 Correct 73 ms 167576 KB Output is correct
61 Correct 208 ms 276848 KB Output is correct
62 Correct 210 ms 276908 KB Output is correct
63 Correct 244 ms 295716 KB Output is correct
64 Correct 249 ms 294828 KB Output is correct
65 Correct 148 ms 189868 KB Output is correct
66 Correct 147 ms 189644 KB Output is correct
67 Correct 75 ms 166676 KB Output is correct
68 Correct 76 ms 166780 KB Output is correct
69 Correct 204 ms 267872 KB Output is correct
70 Correct 214 ms 267908 KB Output is correct
71 Correct 261 ms 284532 KB Output is correct
72 Correct 248 ms 283636 KB Output is correct
73 Correct 159 ms 187788 KB Output is correct
74 Correct 178 ms 187688 KB Output is correct
75 Correct 77 ms 166288 KB Output is correct
76 Correct 88 ms 167260 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 160076 KB Output is correct
2 Correct 56 ms 159996 KB Output is correct
3 Correct 58 ms 159948 KB Output is correct
4 Correct 60 ms 159932 KB Output is correct
5 Correct 58 ms 159436 KB Output is correct
6 Correct 59 ms 159448 KB Output is correct
7 Correct 59 ms 159216 KB Output is correct
8 Correct 62 ms 159288 KB Output is correct
9 Correct 58 ms 159892 KB Output is correct
10 Correct 58 ms 159876 KB Output is correct
11 Correct 59 ms 159920 KB Output is correct
12 Correct 57 ms 159792 KB Output is correct
13 Correct 57 ms 159436 KB Output is correct
14 Correct 57 ms 159384 KB Output is correct
15 Correct 58 ms 159184 KB Output is correct
16 Correct 57 ms 159220 KB Output is correct
17 Correct 59 ms 159872 KB Output is correct
18 Correct 59 ms 159776 KB Output is correct
19 Correct 60 ms 159804 KB Output is correct
20 Correct 59 ms 159808 KB Output is correct
21 Correct 58 ms 159440 KB Output is correct
22 Correct 58 ms 159456 KB Output is correct
23 Correct 57 ms 159224 KB Output is correct
24 Correct 59 ms 159280 KB Output is correct
25 Correct 61 ms 161900 KB Output is correct
26 Correct 61 ms 161840 KB Output is correct
27 Correct 64 ms 163148 KB Output is correct
28 Correct 62 ms 163148 KB Output is correct
29 Correct 60 ms 159896 KB Output is correct
30 Correct 61 ms 159920 KB Output is correct
31 Correct 62 ms 160736 KB Output is correct
32 Correct 60 ms 160656 KB Output is correct
33 Correct 61 ms 160772 KB Output is correct
34 Correct 60 ms 160696 KB Output is correct
35 Correct 61 ms 161356 KB Output is correct
36 Correct 63 ms 161444 KB Output is correct
37 Correct 62 ms 163116 KB Output is correct
38 Correct 61 ms 163176 KB Output is correct
39 Correct 59 ms 159904 KB Output is correct
40 Correct 61 ms 159844 KB Output is correct
41 Correct 60 ms 160636 KB Output is correct
42 Correct 61 ms 160728 KB Output is correct
43 Correct 60 ms 161200 KB Output is correct
44 Correct 60 ms 161228 KB Output is correct
45 Correct 62 ms 162744 KB Output is correct
46 Correct 62 ms 162888 KB Output is correct
47 Correct 60 ms 159900 KB Output is correct
48 Correct 59 ms 159820 KB Output is correct
49 Correct 61 ms 160704 KB Output is correct
50 Correct 62 ms 160780 KB Output is correct
51 Correct 118 ms 211892 KB Output is correct
52 Correct 110 ms 211964 KB Output is correct
53 Correct 119 ms 210384 KB Output is correct
54 Correct 121 ms 210212 KB Output is correct
55 Correct 91 ms 172708 KB Output is correct
56 Correct 86 ms 172492 KB Output is correct
57 Correct 62 ms 161332 KB Output is correct
58 Correct 61 ms 161328 KB Output is correct
59 Correct 62 ms 161356 KB Output is correct
60 Correct 62 ms 161252 KB Output is correct
61 Correct 118 ms 202700 KB Output is correct
62 Correct 117 ms 202864 KB Output is correct
63 Correct 120 ms 208588 KB Output is correct
64 Correct 123 ms 208236 KB Output is correct
65 Correct 144 ms 170656 KB Output is correct
66 Correct 87 ms 170580 KB Output is correct
67 Correct 60 ms 161080 KB Output is correct
68 Correct 61 ms 161044 KB Output is correct
69 Correct 112 ms 199372 KB Output is correct
70 Correct 109 ms 199536 KB Output is correct
71 Correct 120 ms 203148 KB Output is correct
72 Correct 122 ms 202200 KB Output is correct
73 Correct 93 ms 169832 KB Output is correct
74 Correct 89 ms 169916 KB Output is correct
75 Correct 66 ms 161488 KB Output is correct
76 Correct 64 ms 161016 KB Output is correct
77 Correct 203 ms 302056 KB Output is correct
78 Correct 194 ms 302012 KB Output is correct
79 Correct 236 ms 300620 KB Output is correct
80 Correct 229 ms 300556 KB Output is correct
81 Correct 143 ms 194112 KB Output is correct
82 Correct 145 ms 194208 KB Output is correct
83 Correct 73 ms 167600 KB Output is correct
84 Correct 73 ms 167496 KB Output is correct
85 Correct 73 ms 167500 KB Output is correct
86 Correct 73 ms 167576 KB Output is correct
87 Correct 208 ms 276848 KB Output is correct
88 Correct 210 ms 276908 KB Output is correct
89 Correct 244 ms 295716 KB Output is correct
90 Correct 249 ms 294828 KB Output is correct
91 Correct 148 ms 189868 KB Output is correct
92 Correct 147 ms 189644 KB Output is correct
93 Correct 75 ms 166676 KB Output is correct
94 Correct 76 ms 166780 KB Output is correct
95 Correct 204 ms 267872 KB Output is correct
96 Correct 214 ms 267908 KB Output is correct
97 Correct 261 ms 284532 KB Output is correct
98 Correct 248 ms 283636 KB Output is correct
99 Correct 159 ms 187788 KB Output is correct
100 Correct 178 ms 187688 KB Output is correct
101 Correct 77 ms 166288 KB Output is correct
102 Correct 88 ms 167260 KB Output is correct
103 Correct 306 ms 427736 KB Output is correct
104 Correct 289 ms 427724 KB Output is correct
105 Correct 524 ms 516584 KB Output is correct
106 Correct 440 ms 516444 KB Output is correct
107 Correct 196 ms 224772 KB Output is correct
108 Correct 198 ms 224792 KB Output is correct
109 Correct 90 ms 184724 KB Output is correct
110 Correct 90 ms 184720 KB Output is correct
111 Correct 91 ms 184700 KB Output is correct
112 Correct 93 ms 184832 KB Output is correct
113 Correct 291 ms 381100 KB Output is correct
114 Correct 293 ms 380876 KB Output is correct
115 Correct 428 ms 520776 KB Output is correct
116 Correct 434 ms 519252 KB Output is correct
117 Correct 206 ms 220164 KB Output is correct
118 Correct 198 ms 220532 KB Output is correct
119 Correct 92 ms 184272 KB Output is correct
120 Correct 93 ms 184088 KB Output is correct
121 Correct 280 ms 361804 KB Output is correct
122 Correct 282 ms 361880 KB Output is correct
123 Correct 414 ms 501836 KB Output is correct
124 Correct 426 ms 508448 KB Output is correct
125 Correct 217 ms 217932 KB Output is correct
126 Correct 217 ms 218680 KB Output is correct
127 Correct 96 ms 185708 KB Output is correct
128 Correct 93 ms 184780 KB Output is correct