제출 #1125842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125842		peacebringer1667	Vinjete (COI22_vinjete)	C++17	0 / 100	2 ms	2836 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 subtask1{
	bool subtask1(int n,int m){
		return max(n,m) <= 1000;
	}
	const int s1maxn = 105;
	
	int cnt[s1maxn],res[s1maxn];
	
	void dfs(int u,int par,int L,int R,int m){
		for (int i = L ; i <= R ; i++) cnt[i]++;
		for (int i = 1 ; i <= m ; i++) res[u] += (cnt[i] > 0);
		
		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);
		   }
		
		for (int i = L ; i <= R ; i++) cnt[i]--;
	}
	
	void solve(int n,int m){
		dfs(1,0,-1,0,m);
		
		for (int i = 2 ; i <= n ; i++) cout << res[i] << "\n";
	}
}

namespace subtask4{
	bool subtask4(int n,int m){
		return max(n,m) <= 100000;
	}
	
	struct segment_tree{
		int seg[4*maxn],f[4*maxn];
		
		void update(int l,int r,int v,int lx,int rx,int val){
			if (l > rx || r < lx) return;
			if (l >= lx && r <= rx){
				f[v] += val;
				if (!f[v]) seg[v] = (l == r) ? 0 : (seg[2*v + 1] + seg[2*v + 2]);
				if (f[v]) seg[v] = r - l + 1;
			    
			    return;
			}
			
			int w = (l + r)/2;
			update(l,w,2*v + 1,lx,rx,val);
			update(w + 1,r,2*v + 2,lx,rx,val);
			seg[v] = (!f[v]) ? (seg[2*v + 1] + seg[2*v + 2]) : (r - l + 1);
		}
		
		int calc(){
			return seg[0];
		}
	} seg;
	
	int res[maxn];
	
	void dfs(int u,int par,int L,int R,int m){
		if (u > 1){
			seg.update(1,m,0,L,R,1);
			res[u] = seg.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)
		   seg.update(1,m,0,L,R,-1);
	}
	
	void solve(int n,int m){
		dfs(1,0,0,0,m);
		
		for (int i = 2 ; i <= n ; i++) cout << res[i] << "\n";
	}
}

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);
	
	if (subtask1::subtask1(n,m)){
		subtask1::solve(n,m);
		return 0;
	}
	
	//subtask 3 and subtask 4 
	if (subtask4::subtask4(n,m)){
		subtask4::solve(n,m);
		return 0;
	}
	
	//subfull : from subtask4, dynamic segment tree
	subfull::solve(n,m);

	return 0;
}

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