Submission #981607

#	Time	Username	Problem	Language	Result	Execution time	Memory
981607		vjudge1	Road Closures (APIO21_roads)	C++17	0 / 100	38 ms	20572 KiB

roads

#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
using namespace std;
const int mxn=1e5+5;
vector<pii>g[mxn];int d[mxn]{0};
struct node{
    ll tt;int cr;
    node *l,*r;
    node(int x,int y) : tt(x),cr(y),l(NULL),r(NULL){};
    node(node *l,node *r) : tt(l->tt+r->tt),cr(l->cr+r->cr),l(l),r(r){};
};
node*rt[mxn];
node* upd(node*t,ll l,ll r,ll val){
    if(t==NULL)t=new node(0,0);
    if(l==r)return new node(t->tt+val,t->cr+1);
    ll m=(l+r)>>1;
    if(val<=m)return new node(upd(t->l,l,m,val),t->r);
    else return new node(t->l,upd(t->r,m+1,r,val));
}
vll minimum_closure_costs(int N,vi U,vi V,vi W){vll ans(N,0);
    for(int i=0;i<N-1;i++)g[U[i]].pb({V[i],W[i]}),g[V[i]].pb({U[i],W[i]});
    for(int i=0;i<N;i++)for(auto v:g[i])rt[i]=upd(rt[i],-1e14,1e14,-v.s);
    return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22