oj.uz

Submission #850720

# Submission time Handle Problem Language Result Execution time Memory
850720 2023-09-17T10:51:58 Z TahirAliyev Vinjete (COI22_vinjete) C++17
0 / 100
 2 ms 344 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define oo 2e9
#define pii pair<ll, int>

const int MAX = 1002, LOGMAX = 31, treesize = MAX * LOGMAX;
int n, m;
vector<array<int, 3>> g[MAX];

pii tree[treesize];
int L[treesize], R[treesize], lazy[treesize];

void relax(int node){
    if(!lazy[node]) return;
    tree[node].first += lazy[node];
    if(L[node]){
        lazy[L[node]] += lazy[node];
    }
    if(R[node]){
        lazy[R[node]] += lazy[node];
    }
    lazy[node] = 0;
}

int nxt = 2;

pii combine(pii a, pii b){
    if(a.first == b.first){
        return {a.first, a.second + b.second};
    }
    return min(a, b);
}

void update(int node, int l, int r, int ul, int ur, int val){
    relax(node);
    if(ur < l || r < ul) return;
    if(ul <= l && r <= ur){
        lazy[node] += val;
        relax(node);
        return;
    }
    int mid = (l + r) / 2;
    if(!L[node]){
        L[node] = nxt++;    
        tree[L[node]] = {0, mid - l + 1};
    }   
    if(!R[node]){
        R[node] = nxt++;
        tree[R[node]] = {0, r - mid};
    }
    update(L[node], l, mid, ul, ur, val);
    update(R[node], mid + 1, r, ul, ur, val);
    tree[node] = combine(tree[L[node]], tree[R[node]]);
}

int ans[MAX];

void dfs(int node, int p, int l, int r){
    if(node != 1){
        update(1, 1, m, l, r, 1);
    }
    if(tree[1].first == 0){
        ans[node] = m - tree[1].second;
    }
    else{
        ans[node] = m;
    }
    for(auto to : g[node]){
        if(p == to[0]) continue;
        dfs(to[0], node, to[1], to[2]);
    }
    if(node != 1){
        update(1, 1, m, l, r, -1);
    }
}


int main(){
    cin >> n >> m;
    for(int i = 1; i < n; i++){
        int a, b, l, r; cin >> a >> b >> l >> r;
        g[a].push_back({b, l, r});
        g[b].push_back({a, l, r});
    }
    tree[1] = {0, m};
    dfs(1, 1, 0, 0);
    for(int i = 2; i <= n; i++){
        cout << ans[i] << '\n';
    }
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -