Submission #846872

#	Time	Username	Problem	Language	Result	Execution time	Memory
846872		Cookie	Vinjete (COI22_vinjete)	C++14	100 / 100	422 ms	150416 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define vt vector
#define pb push_back
#define pii pair<int, int>
#define sz(v) (int)v.size()
#define fi first
#define se second
using namespace std;
const ll base = 107, mod = 1e9 + 7;
const int mxn = 1e5 + 5, N = 8e6 + 5;
struct Node{
    int mn = 0, cnt = 0, lz = 0;
    Node(){
        mn = cnt = lz = 0;
    }
    Node(int _mn, int _cnt, int _lz){
        mn = _mn; cnt = _cnt; lz = _lz;
    }
};
int n, m;
vt<pii>adj[mxn + 1];
int lp[mxn + 1], rp[mxn + 1], id = 1, ans[mxn + 1], toedge[mxn + 1];
int lson[N], rson[N];
Node st[N];
void push(int nd, int l, int mid, int r){
    int &v = st[nd].lz;
    if(!lson[nd]){
        //cout << nd << " ";
        lson[nd] = ++id; st[id].cnt = mid - l + 1; 
        rson[nd] = ++id; st[id].cnt = r - mid;
    }
    //cout << l << " " << r << " " << v << "\n";
    st[lson[nd]].lz += v; st[lson[nd]].mn += v;
    st[rson[nd]].lz += v; st[rson[nd]].mn += v;
    v = 0;
    st[nd].lz = 0;
    assert(st[nd].lz == 0);
}
Node comb(Node a, Node b){
    if(a.mn < b.mn){
        Node res; res.mn = a.mn; res.cnt = a.cnt;
        return(res);
    }
    if(a.mn > b.mn){
        Node res; res.mn = b.mn; res.cnt = b.cnt;
        return(res);
    }
    Node res; res.mn = a.mn;
    res.cnt = a.cnt + b.cnt; res.lz = 0;
    return(res);
}
void upd(int nd, int l, int r, int ql, int qr, int v){
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        st[nd].mn += v; st[nd].lz += v;
        
        return;
    }
    
    int mid = (l + r) >> 1;
    push(nd, l, mid, r);
    
    upd(lson[nd], l, mid, ql, qr, v); upd(rson[nd], mid + 1, r, ql, qr, v);
    assert(st[nd].lz == 0);
    st[nd] = comb(st[lson[nd]], st[rson[nd]]);
    assert(st[nd].lz == 0);
}
void dfs(int s, int pre){
    
    //cout << s << " " <<  st[1].mn << "\n";
    if(st[1].mn != 0)ans[s] = 0;
    else ans[s] = st[1].cnt;
    for(int i = 0; i < sz(adj[s]); i++){
        int v = adj[s][i].first, id = adj[s][i].second;
        if(v == pre)continue;
        toedge[v] = id;
        upd(1, 1, m, lp[id], rp[id], 1);
        
        
        dfs(v, s);
        upd(1, 1, m, lp[id], rp[id], -1);
        
    }
    //cout << s << " " <<  st[1].mn << "\n";
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    st[1].cnt = m;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v >> lp[i] >> rp[i];
        adj[u].pb({v, i}); adj[v].pb({u, i});
        
    }
    dfs(1, -1);
    for(int i = 2; i <= n; i++){
      assert(ans[i] <= m);
      cout << m - ans[i] << "\n";
    }
}

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