Submission #953469

#	Time	Username	Problem	Language	Result	Execution time	Memory
953469		dwuy	Vinjete (COI22_vinjete)	C++14	100 / 100	531 ms	193920 KiB

Main

/**   - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;  

struct Node{
    int cnt;
    int sum;
    Node *l, *r;

    Node(){
        this->cnt = 0;
        this->sum = 0;
        this->l = this->r = NULL;
    }
};

struct SMT{
    Node *root;
    int n;

    SMT(int n = 0){
        this->n = n;
        this->root = new Node();
    }
    
    Node *update(int l, int r, Node *cur, const int &u, const int &v, const int &val){
        if(l>v || r<u) return cur;
        if(cur == NULL) cur = new Node();
        if(l>=u && r<=v){
            cur->cnt += val;
            cur->sum = cur->cnt? r - l + 1 : (cur->l? cur->l->sum : 0) + (cur->r? cur->r->sum : 0);
            return cur;
        }
        int mid = (l+r)>>1;
        cur->l = update(l, mid, cur->l, u, v, val);
        cur->r = update(mid+1, r, cur->r, u, v, val);
        cur->sum = cur->cnt? r - l + 1 : (cur->l? cur->l->sum : 0) + (cur->r? cur->r->sum : 0);
        return cur;
    }

    void update(int l, int r, int val){
        root = update(1, n, root, l, r, val);
    }

    int get(int l, int r, Node *cur, const int &u, const int &v){
        if(l>v || r<u || cur == NULL) return 0;
        if(l>=u && r<=v) return cur->sum;
        int mid = (l+r)>>1;
        if(cur->cnt) return min(r, v) - max(l, u) + 1;
        return get(l, mid, cur->l, u, v) + get(mid+1, r, cur->r, u, v);
    }

    int get(int l, int r){
        return get(1, n, root, l, r);
    }
};

int n, m;
int ans[MX];
pii val[MX];
pii edges[MX];
vector<int> G[MX];

void nhap(){
    cin >> n >> m;
    for(int i=1; i<n; i++){
        int u, v, l, r;
        cin >> u >> v >> l >> r;
        G[u].push_back(i);
        G[v].push_back(i);
        edges[i] = {u, v};
        val[i] = {l, r};
    }
}

SMT smt(1000000000);

void dfs(int u, int p){
    ans[u] = smt.root->sum;
    for(int i: G[u]){
        int v = edges[i].fi ^ edges[i].se ^ u;
        if(v == p) continue;
        int l, r; tie(l, r) = val[i];
        smt.update(l, r, 1);        
        dfs(v, u);
        smt.update(l, r, -1);
    }
}

void solve(){
    dfs(1, 0);
    for(int i=2; i<=n; i++) cout << ans[i] << endl;
}

int32_t main(){
    fastIO;
    //file(TASK);
    
    nhap();
    solve();

    return 0;
}

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