Submission #767237

#	Time	Username	Problem	Language	Result	Execution time	Memory
767237		Dan4Life	Vinjete (COI22_vinjete)	C++17	100 / 100	551 ms	520840 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)1e5+10;
const int mxN2 = mxN*400;
int n, mx, IND = 1;
int seg[mxN2], lzy[mxN2];
vector<array<int,3>> adj[mxN];
int ans[mxN], ro[mxN], L[mxN2], R[mxN2];

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));
}

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

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> mx; ro[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].push_back({b,l,r}), adj[b].push_back({a,l,r});
	}
	dfs(1,0);
	for(int i = 2; i <= n; i++) cout << ans[i] << "\n";
}

Compilation message (stderr)

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

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31