Submission #767224

#	Time	Username	Problem	Language	Result	Execution time	Memory
767224		Dan4Life	Vinjete (COI22_vinjete)	C++17	100 / 100	492 ms	522108 KiB

Main

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

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 (stderr)

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);
      |                                        ^~~~

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