Submission #1123692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123692		ro9669	Vinjete (COI22_vinjete)	C++17	100 / 100	604 ms	148076 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(2e5)+7;

struct node{
    int lef , rig , val , cnt;
    node(){
        lef = rig = -1;
        val = cnt = 0;
    }
};

vector<node> st;

int lefID(int id){
    if (id == -1) return -1;
    return st[id].lef;
}

int rigID(int id){
    if (id == -1) return -1;
    return st[id].rig;
}

int getVal(int id){
    if (id == -1) return 0;
    return st[id].val;
}

void modify(int id , int l , int r){
    if (st[id].cnt > 0){
        st[id].val = r - l + 1;
    }
    else{
        st[id].val = getVal(lefID(id)) + getVal(rigID(id));
    }
}

void update(int id , int l , int r , int u , int v , int x){
    if (v < l || r < u) return;
    if (u <= l && r <= v){
        st[id].cnt += x;
        modify(id , l , r);
        return;
    }
    int mid = (l + r) / 2;
    if (lefID(id) == -1){
        st.push_back(node());
        st[id].lef = sz(st) - 1;
    }
    if (rigID(id) == -1){
        st.push_back(node());
        st[id].rig = sz(st) - 1;
    }
    update(lefID(id) , l , mid , u , v , x);
    update(rigID(id) , mid + 1 , r , u , v , x);
    modify(id , l , r);
}

int n , m , L[maxN] , R[maxN] , res[maxN];
vector<ii> g[maxN];

void dfs(int u , int par){
    res[u] = st[0].val;
    for (auto e : g[u]){
        int v = e.fi;
        int id = e.se;
        if (v != par){
            update(0 , 1 , m , L[id] , R[id] , +1);
            dfs(v , u);
            update(0 , 1 , m , L[id] , R[id] , -1);
        }
    }
}

void solve(){
    cin >> n >> m;
    for (int i = 1 ; i < n ; i++){
        int u , v;
        cin >> u >> v >> L[i] >> R[i];
        g[u].push_back({v , i});
        g[v].push_back({u , i});
    }
    st.push_back(node());
    dfs(1 , 0);
    for (int i = 2 ; i <= n ; i++) cout << res[i] << "\n";
}

#define name "A"

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(name".INP" , "r")){
        freopen(name".INP" , "r" , stdin);
        freopen(name".OUT" , "w" , stdout);
    }
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(name".INP" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(name".OUT" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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