Submission #846747

#	Time	Username	Problem	Language	Result	Execution time	Memory
846747		Cookie	Vinjete (COI22_vinjete)	C++14	0 / 100	3 ms	7512 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 = 3e6 + 5;
struct Node{
    int mn, cnt, lz;
    Node(){};
    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]){
        lson[nd] = ++id; st[id].cnt = mid - l + 1; 
        rson[nd] = ++id; st[id].cnt = r - mid;
    }
    st[lson[nd]].lz += v; st[lson[nd]].mn += v;
    st[rson[nd]].lz += v; st[rson[nd]].mn += v;
    v = 0;
}
Node comb(Node a, Node b){
    if(a.mn < b.mn)return(a);
    if(a.mn > b.mn)return(b);
    return(Node(a.mn, a.cnt + b.cnt, 0));
}
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);
    st[nd] = comb(st[lson[nd]], st[rson[nd]]);
    //cout << l << " " << r << " " << st[nd].cnt << " " << st[nd].mn << "\n";
}
void dfs(int s, int pre){
    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);
    }
    if(s != 1)upd(1, 1, m, lp[toedge[s]], rp[toedge[s]], -1);
}
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++)cout << m - ans[i] << "\n";
}

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