Submission #748291

#	Time	Username	Problem	Language	Result	Execution time	Memory
748291		Cookie	Vinjete (COI22_vinjete)	C++14	0 / 100	16 ms	24020 KiB

Main

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("VNOICUP.INP");
ofstream fout("VNOICUP.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
//const int x[4] = {1, -1, 0, 0};
//const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 1e6 + 5, mxq = 1e6 + 5, sq = 400;
const int base = (1 << 18);
const int inf = 1e9, neg = -69420;
struct th{
    int v, l, r;
};
int n, m;
set<pll> ms;
vt<th>adj[mxn + 1];
ll val = 0, ans[mxn + 1];
vt<ll>preval; 
vt<vt<pll>>rem;
vt<vt<pll>>add;
void calc(int s, ll l, ll r){
    preval.pb(val);   
    vt<pll>v1;
    ll mn = l, mx = r;
    auto hg = ms.lower_bound({l, -1});
    for(auto it = hg; it != ms.end(); ++it){
        auto seg = *it;
        if(seg.se > r)break;
        else{
            mn = min(mn, seg.se); mx = max(mx, seg.fi);
            v1.pb(seg); val -= seg.fi - seg.se + 1;
        }
    }
    val += mx - mn + 1; 
    for(auto i: v1){
        ms.erase(i);
    }
    rem.pb(v1);
    add.pb({make_pair(mx, mn)}); ms.insert({mx, mn});
}
void rollback(){
    if(!preval.size())return;
    val = preval.back(); preval.pop_back();
    auto v1 = rem.back(), v2 = add.back();
    rem.pop_back(); add.pop_back();
    for(auto i: v1){
        ms.insert(i);  
    }
    for(auto i: v2){
        ms.erase(i);
    }
}
void dfs(int s, int pre){
    
    ans[s] = val;
    for(auto [v, l, r]: adj[s]){
        if(v != pre){
            calc(v, l, r);
            dfs(v, s);
            
        }
    }
    rollback();
    
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    ms.insert({-1, -1}); ms.insert({m + 1, m + 1});
    forr(i, 1, n){
        int u, v, l, r; cin >> u >> v >> l >> r;
        adj[u].pb({v, l, r}); adj[v].pb({u, l, r});
    }
    dfs(1, -1);
    forr(i, 2, n + 1)cout << ans[i] << "\n";
    return(0);
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:71:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |     for(auto [v, l, r]: adj[s]){
      |              ^

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