제출 #1320189

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320189		WH8	Vinjete (COI22_vinjete)	C++17	100 / 100	898 ms	310336 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define pb push_back
#define f first
#define s second
#define ld long double
#define sz(x) static_cast<int>((x).size())
#define i5 tuple<int,int,int,int,int>
#define all(x) x.begin(), x.end()
#define iii tuple<int,int,int>
#define eb emplace_back
#define mt make_tuple
#define pll pair<int,int>

#include <bits/stdc++.h>
using namespace std;
#define int long long
pll combine(pll a, pll b){
	if(a.f==b.f)return mp(a.f, a.s+b.s);
	return min(a, b);
}
struct node {
    node *left, *right;
    int S, E, lazy;
	pll v;
    node(int _s, int _e) : S(_s), E(_e) {
        left = right = nullptr;
        v=mp(0ll,(E-S+1));
        lazy = 0;
    }
    void prop(){
        if(S == E) return;
        int M = (S + E) / 2;
        if(left == nullptr){ // no children
            left = new node(S, M);
            right = new node(M + 1, E);
        }
        if(lazy != 0){
            left->v.f += lazy;
            left->lazy += lazy;
            right->v.f += lazy;
            right->lazy += lazy;
            lazy = 0;
        }
    }
    pll qry(int l, int r) { // sum from index l to index r
        if (l > E || r < S) {
            return mp(1e15, 0);
        }
        if (l <= S && E <= r) {
            return v;
        }
        prop();
        return combine(left->qry(l, r), right->qry(l, r));
    }
    void upd(int l, int r, int dv) {
        if (l > E || r < S) {
            return;
        }
        if (l <= S && E <= r) {
            v.f += dv;
            lazy += dv;
            return;
        }
        prop();
        left->upd(l, r, dv);       
        right->upd(l, r, dv);
        v = combine(left->v, right->v);
		//printf("segment %lld %lld v.f %lld, v.s %lld, lvf %lld lvs %lld rvf %lld rvs %lld \n", S, E,v.f, v.s, left->v.f, left->v.s, right->v.f, right->v.s);
    }
} *root;
 
signed main(){
	int n, m;cin>>n>>m;
	vector<vector<iii>> al(n+1);
	for(int i=0;i<n-1;i++){
		int a,b,l,r;cin>>a>>b>>l>>r;
		al[a].pb(mt(b,l,r));
		al[b].pb(mt(a,l,r));
	}
	root=new node(1, m);
	int cans=0;
	vector<int> ans(n+1, 0);
	auto dfs=[&](auto && dfs, int x, int p)->void{
		ans[x]=cans;
		//printf("x %lld\n", x);
		/*for(int i=1;i<=m;i++){
			cout<<root->qry(i, i).f<<" ";
		}
		cout<<endl;*/
		for(auto [it, l, r] : al[x]){
			if(it==p)continue;
			auto [v, c] = root->qry(l, r);
			//printf("x %lld, going to %lld, l %lld, r %lld, v %lld, c %lld\n",
		//			x,it,l,r,v,c);
			root->upd(l, r, 1);
			if(v == 0) cans += c;
			dfs(dfs, it, x);
			root->upd(l, r, -1);
			if(v==0)cans-=c;
		}
	};
	dfs(dfs, 1, 0);
	for(int i=2;i<=n;i++)cout<<ans[i]<<'\n';
}

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