제출 #1075711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1075711		_8_8_	Petrol stations (CEOI24_stations)	C++17	0 / 100	935 ms	275792 KiB

Main

#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 7e4 + 12, MOD = 998244353;

mt19937 rng(123231);
struct node{
    node *l = 0,*r = 0;
    ll prior = 0,rem = 0,col = 0,sum =0 ,add = 0;
    node(ll val,ll c){
        prior = rng();
        rem = val;
        col = sum = c;
    }
    node(){
    }
};
using pnode = node *;
int sum(pnode v) {
    return v ? v->sum : 0;
}
void upd(pnode x) {
    x->sum = sum(x->l) + sum(x->r) + x->col;
}
void inc(pnode v,int val) {
    if(v) {
        v->rem += val;
        v->add += val;
    }
}
void push(pnode v) {
    inc(v->l,v->add);
    inc(v->r,v->add);
    v->add = 0;
}
pnode merge(pnode a,pnode b) {
    if(!a) return b;
    if(!b) return a;
    if(a->prior < b->prior) {
        push(b);
        b->l = merge(a,b->l);
        upd(b);
        return b;
    } else {
        push(a);
        a->r = merge(a->r,b);
        upd(a);
        return a;
    }
}
pair<pnode,pnode> split(pnode v,int key) {
    if(!v) return {0,0};
    push(v);
    if(v->rem < key) {
        auto [l,r] = split(v->r,key);
        v->r = l;
        upd(v);
        return {v,r};
    } else {
        auto [l,r] = split(v->l,key);
        v->l = r;
        upd(v);
        return {l,v};
    }   
}
vector<pair<int,int>> g[N];
vector<int> G[N];
int n, k, s[N];
bool blocked[N];
void prec(int v,int pr = -1) {
    s[v] = 1;
    for(int to:G[v]) {
        if(to == pr || blocked[to]) continue;
        prec(to,v);
        s[v] += s[to];
    }
}
int find(int v,int pr,int total) {
    for(int to:G[v]) {
        if(to == pr || blocked[to]) continue;
        if(s[to] > total / 2) {
            return find(to,v,total);
        }
    }
    return v;
}
ll ans[N];
pnode root;
void go(int v,int pr,ll W) {
    auto [l,r] = split(root,W);
    int _s = sum(l);
    root = merge(r,new node(k - W,_s));
    inc(r,-W);
    ans[pr] += _s * 1ll * s[v];
    for(auto [to,w]:g[v]) {
        if(to == pr || blocked[to]) continue;
        go(to,v,w);
    }
    inc(r,W);
    root = merge(l,r);
}
int rem[N],cc[N];
void ins(int val) {
    auto [l,r] = split(root,val);
    pnode nv = new node(val,1);
    root = merge(merge(l,nv),r);
}
void cl(int v,int pr) {
    cc[v] = 0;
    for(int to:G[v]) if(!blocked[to] && to != pr) {
        cl(to,v);
    }
}
int total,pt;
bool REV = false;
void add(int v,int pr, vector<pair<int,int>> &st) {
    ll c = k;
    rem[v] = -1;
    int vert = -1,aft;
    for(int i = (int)st.size() - 1;i >= 0;i--) {
        c -= st[i].second;
        if(c < 0) {
            rem[v] = rem[st[i].first];
            vert = st[i +1].first;
            break;
        }
    }
    if(rem[v] == -1) {
        rem[v] = c;
    }
    ins(rem[v]);  
    cc[v]++;
    for(auto [to,w]:g[v]) {
        if(to == pr || blocked[to]) continue;
        st.push_back({v,w});
        add(to,v,st);
        st.pop_back();
    }
    if(vert != -1) {
        cc[vert] += cc[v];
        if(!REV) ans[vert] += cc[v] * (total - s[pt]);
    }
}
void decompose(int v) {
    prec(v);
    v = find(v,-1,s[v]);
    blocked[v] = 1;
    prec(v);
    total = s[v];
    root = new node();
    rem[v] = k;
    ins(k);
    REV = false;
    cc[v] = 0;
    for(auto [to,w]:g[v]) if(!blocked[to]) {
        go(to,v,w);
        vector<pair<int,int>> bf = {make_pair(v,w)};
        cl(to,v);
        pt =to;
        add(to,v,bf);
    }
    root = new node();
    reverse(g[v].begin(),g[v].end());
    REV = 1;
    for(auto [to,w]:g[v]) if(!blocked[to]) {
        go(to,v,w);
        vector<pair<int,int>> bf = {make_pair(to,w)};
        cl(to,v);
        add(to,v,bf);
    }
    for(int to:G[v]) if(!blocked[to]) {
       decompose(to);
    }
}
void test() {
    cin >> n >> k;
    for(int i = 1; i <= n - 1; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        a++;
        b++;
        g[a].push_back({b,c});G[a].push_back(b);
        g[b].push_back({a,c});G[b].push_back(a);
    }
    decompose(1);
    for(int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void add(int, int, std::vector<std::pair<int, int> >&)':
Main.cpp:121:19: warning: unused variable 'aft' [-Wunused-variable]
  121 |     int vert = -1,aft;
      |                   ^~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 18
• Subtask 2: 0 / 8
• Subtask 3: 0 / 10
• Subtask 4: 0 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 35