제출 #1277711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277711		dosts	Vinjete (COI22_vinjete)	C++20	100 / 100	314 ms	71784 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

const int N = 1e5+1;
vector<pair<int,pii>> edges[N];
vector<pii> v2;
vi ans(N);

struct ST {
    vector<pii> t;
    vi lazy;
    pii merge(pii p2,pii p3) {
        if (p2.ff < p3.ff) return p2;
        else if (p2.ff > p3.ff) return p3;
        else return {p2.ff,p2.ss+p3.ss};
    }
    void build(int node,int l,int r) {
        if (l == r) {
            //cout << "E" sp l sp v2[l-1].ff sp v2[l-1].ss << endl;
            t[node] = {0,v2[l-1].ss};
            return;
        }
        int m = (l+r) >> 1;
        build(2*node,l,m),build(2*node+1,m+1,r);
        t[node] = merge(t[2*node],t[2*node+1]);
    }

    ST(){}
    ST(int nn) {
        lazy.assign(4*nn+1,0);
        t.resize(4*nn+1);
        build(1,1,nn);
    }

    void push(int node,bool leaf) {
        if (!lazy[node]) return;
        t[node].ff+=lazy[node];
        if (!leaf){
            lazy[2*node]+=lazy[node];
            lazy[2*node+1]+=lazy[node];
        }
        lazy[node] = 0;
    }

    pii query(int node,int l,int r,int L,int R) {
        push(node,l==r);
        if (l > R || r < L) return {inf,0};
        if (l >= L && r <= R) return t[node];
        int m = (l+r) >> 1;
        return merge(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
    }

    void update(int node,int l,int r,int L,int R,int v) {
        push(node,l==r);
        if (l > R || r < L) return;
        if (l >= L && r <= R) {
            lazy[node]+=v;
            push(node,l==r);
            return;
        }
        int m = (l+r) >> 1;
        update(2*node,l,m,L,R,v),update(2*node+1,m+1,r,L,R,v);
        t[node] = merge(t[2*node],t[2*node+1]);
    }
}st;

int idx(int x) {
    return upper_bound(all(v2),pii{x,inf})-v2.begin();
}

int sz;
void dfs(int node,int p) {
    //cout <<" ENTER " sp node << endl;
    //for (int j = 1;j<=sz;j++) cout << '(' sp st.query(1,1,sz,j,j).ff sp st.query(1,1,sz,j,j).ss sp ')' << ' ';
    //cout << '\n';
    pii qq = st.query(1,1,sz,1,sz);
    //cout << qq.ff sp qq.ss << endl;
    ans[node] = (!qq.ff)?(qq.ss):0ll;
    for (auto it : edges[node]) {
        if (it.ff == p) continue;
        int le = idx(it.ss.ff),ri = idx(it.ss.ss);
        //cout << "+" sp le sp ri << endl;
        st.update(1,1,sz,le,ri,1);
        dfs(it.ff,node);
        st.update(1,1,sz,le,ri,-1);
        //cout << "-" sp le sp ri << endl;
    }
}

void solve() {
    int n,m;
    cin >> n >> m;
    vi v;
    for (int i=1;i<=n-1;i++) {
        int a,b,l,r;
        cin >> a >> b >> l >> r;
        v.push_back(l);
        v.push_back(r);
        edges[a].push_back({b,{l,r}});
        edges[b].push_back({a,{l,r}});
    }
    sort(all(v));
    v.erase(unique(v.begin(),v.end()),v.end());
    if (v[0] != 1) v.insert(v.begin(),1);
    if (v.back() != m) v.push_back(m);
    for (int i = 0;i<big(v)-1;i++) {
        if (v[i+1]-v[i] > 1) v2.push_back({v[i]+1,v[i+1]-v[i]-1});
        v2.push_back({v[i],1});
    }
    v2.push_back({v.back(),1});
    sort(all(v2));
    sz = big(v2);
    st = ST(sz);
    dfs(1,1);
    for (int i=2;i<=n;i++) cout << m-ans[i] << '\n';
} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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