제출 #1125843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125843		peacebringer1667	Vinjete (COI22_vinjete)	C++17	100 / 100	792 ms	178228 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 1e5 + 5;

template <class t1,class t2> inline void maxi(t1 &x,t2 y){if (x < y) x = y;}
template <class t1,class t2> inline void mini(t1 &x,t2 y){if (x > y) x = y;}

struct edge{
	int v = 0,l = 0,r = 0;
};

vector <edge> vec[maxn];

void input(int n,int m){
	for (int i = 1 ; i < n ; i++){
		int u,v,l,r;
		cin >> u >> v >> l >> r;
		vec[u].push_back({v,l,r});
		vec[v].push_back({u,l,r});
	}
}

namespace subfull{
	vector <int> seg(1),f(1),L(1),R(1);
	
	int res[maxn];
	
	void update(int l,int r,int v,int lx,int rx,int val){
		//create two new child nodes
		if (l != r){
			if (!L[v]){
				L[v] = seg.size();
				L.push_back(0);
				R.push_back(0);
				seg.push_back(0);
			    f.push_back(0);
			}
			if (!R[v]){
				R[v] = seg.size();
				L.push_back(0);
				R.push_back(0);
				seg.push_back(0);
				f.push_back(0);
			}
	    }
		//////////
		
		if (l > rx || r < lx) return;
		if (l >= lx && r <= rx){
			f[v] += val;
			
			if (!f[v]) seg[v] = (l == r) ? 0 : (seg[L[v]] + seg[R[v]]);
			if (f[v]) seg[v] = r - l + 1;
			
			return;
		}
		
		int w = (l + r)/2;
		update(l,w,L[v],lx,rx,val);
		update(w + 1,r,R[v],lx,rx,val);
		seg[v] = (f[v]) ? (r - l + 1) : (seg[L[v]] + seg[R[v]]);
	}
	
	int calc(){
		return seg[0];
	}
	
	void dfs(int u,int par,int lx,int rx,int m){
		if (u > 1){
			update(1,m,0,lx,rx,1);
			res[u] = calc();
		}
		
		for (edge e : vec[u])
		   if (e.v != par){
		   	   int v = e.v,l = e.l,r = e.r;
		   	   dfs(v,u,l,r,m);
		   }
		
		if (u > 1)
		   update(1,m,0,lx,rx,-1);
	}
	
	void solve(int n,int m){
		dfs(1,0,0,0,m);
		seg.clear();L.clear(),R.clear(),f.clear();
		
		for (int u = 2 ; u <= n ; u++) cout << res[u] << "\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
//	freopen("HIGHWAY.inp","r",stdin);
//	freopen("HIGHWAY.out","w",stdout);
	
	int n,m;
	cin >> n >> m;
	input(n,m);
	
	//subfull : from subtask4, dynamic segment tree
	subfull::solve(n,m);

	return 0;
}

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