Submission #959908

#	Time	Username	Problem	Language	Result	Execution time	Memory
959908		pcc	Vinjete (COI22_vinjete)	C++17	100 / 100	346 ms	189636 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long

const int mxn = 1e5+10;
const int inf = 1e9+10;

struct SEG{
#define ls seg[now].pl
#define rs seg[now].pr
#define mid ((l+r)>>1)
	struct node{
		int pl,pr,tag,cnt;
		node(){
			pl = pr = tag = cnt = 0;
		}
	};
	node seg[mxn*100];
	int ppp = 0;
	int newnode(){
		return ++ppp;
	}
	int modify(int now,int l,int r,int s,int e,int v){
		if(!now)now = newnode();
		if(l>=s&&e>=r){
			seg[now].tag += v;
			return now;
		}
		if(mid>=s)ls = modify(ls,l,mid,s,e,v);
		if(mid<e)rs = modify(rs,mid+1,r,s,e,v);
		seg[now].cnt = (seg[ls].tag?mid-l+1:seg[ls].cnt)+(seg[rs].tag?r-mid:seg[rs].cnt);
		return now;
	}
#undef ls
#undef rs
#undef mid
};

SEG seg;
int N,M;
vector<pii> tree[mxn];
pii edges[mxn];
int ans[mxn];
int rt;

void dfs(int now,int par){
	ans[now] = seg.seg[rt].cnt;
	for(auto [nxt,eid]:tree[now]){
		if(nxt == par)continue;
		auto [l,r] = edges[eid];
		rt = seg.modify(rt,0,M,l,r,1);
		dfs(nxt,now);
		rt = seg.modify(rt,0,M,l,r,-1);
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i = 1;i<N;i++){
		int a,b,s,e;
		cin>>a>>b>>s>>e;
		edges[i] = pii(s,e);
		tree[a].push_back(pii(b,i));
		tree[b].push_back(pii(a,i));
	}
	dfs(1,1);
	rt = seg.newnode();
	for(int i = 2;i<=N;i++)cout<<ans[i]<<'\n';
	return 0;
}

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