Submission #735106

#	Time	Username	Problem	Language	Result	Execution time	Memory
735106		PoonYaPat	Road Closures (APIO21_roads)	C++14	0 / 100	2079 ms	25840 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int n,d[100001],p[100001],level[100001];
ll dp[100001][2],w[100001],sum;
vector<int> deg[100001];
vector<pii> adj[100001];
vector<ll> ans;
bool vis[100001];

bool comp(pii a, pii b) {return a.second<b.second;}
bool comp2(int a, int b) {return level[a]>level[b];}

struct node {
    int cnt,prior;
    ll val,sum;
    node *l, *r;

    node(ll v) : cnt(1), val(v), sum(v), prior(rand()), l(NULL), r(NULL) {}
};
typedef node* pnode;
pnode tr[100001];

void upd(pnode t) {
    if (t) {
        t->cnt=1;
        t->sum=t->val;
        if (t->l) {
            t->cnt+=t->l->cnt;
            t->sum+=t->l->sum;
        }
        if (t->r) {
            t->cnt+=t->r->cnt;
            t->sum+=t->r->sum;
        }
    }
}

int get_cnt(pnode t) {
    if (!t) return 0;
    else return t->cnt;
}

void split1(pnode t, pnode &l, pnode &r, int v) { //split by cnt
    if (t==NULL) l=r=NULL;
    else if (get_cnt(t->l)>=v) split1(t->l,l,t->l,v), r=t;
    else split1(t->r,t->r,r,v-get_cnt(t->l)-1), l=t;
    upd(t);
}

void split2(pnode t, pnode &l, pnode &r, int v) { //split by val
    if (t==NULL) l=r=NULL;
    if (t->val>=v) split2(t->l,l,t->l,v), r=t;
    else split2(t->r,t->r,r,v), l=t;
    upd(t);
}

void merge(pnode l, pnode r, pnode &t) {
    if (!l) t=r;
    else if (!r) t=l;
    else if (l->prior>=r->prior) merge(l->r,r,l->r), t=l;
    else merge(l,r->l,r->l), t=r;
    upd(t);
}

void dfs(int x, int par) {
    p[x]=par;
    level[x]=level[par]+1;
    for (auto s : adj[x]) {
        if (s.first==par) continue;
        w[s.first]=s.second;
        merge(tr[x],new node(s.second),tr[x]);
        dfs(s.first,x);
    }
}

void cal(int x, int want) {
    pnode A,B,C;
    ll pre=dp[x][1]-dp[x][0];

    //find dp[x][0], don't cut the edge above it

    split1(tr[x],A,B,adj[x].size()-want);
    if (A) dp[x][0]=A->sum;
    else dp[x][0]=0;
    merge(A,B,tr[x]);

    if (x) {
        //find dp[x][1], cut the edge above it

        split1(tr[x],A,B,adj[x].size()-want-1);
        if (A) dp[x][1]=A->sum+w[x];
        else dp[x][1]=w[x];
        merge(A,B,tr[x]);

        //replace the value of the parent by dp[x][1]-dp[x][0]

        int par=p[x];
        split2(tr[par],A,B,pre);
        split1(B,C,B,1);
        assert(C->val==pre);
        merge(A,B,tr[par]);

        ll nw=dp[x][1]-dp[x][0];
        split2(tr[par],A,B,nw+1);
        merge(A,new node(nw),A);
        merge(A,B,tr[par]);
    }
}

vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
    n=N;
    for (int i=0; i<n-1; ++i) {
        adj[U[i]].push_back(pii(V[i],W[i]));
        adj[V[i]].push_back(pii(U[i],W[i]));
        ++d[U[i]]; ++d[V[i]];
    }
    for (int i=0; i<n; ++i) deg[d[i]].push_back(i), sort(adj[i].begin(),adj[i].end(),comp);
    dfs(0,0);
    p[0]=-1;
    for (int i=1; i<n; ++i) dp[i][1]=w[i], sum+=w[i];
    ans.push_back(sum);

    for (int i=1; i<n; ++i) {
        sum=0;
        vector<int> v;
        for (int j=i+1; j<n; ++j) for (auto s : deg[j]) v.push_back(s);
        sort(v.begin(),v.end(),comp2);

        for (auto s : v) {
            if (n<=30000) cal(s,i);
            if (d[p[s]]<=i && p[s]!=-1) sum+=min(dp[s][0],dp[s][1]);
            else sum+=dp[s][0];
        }

        ans.push_back(sum);
    }

    return ans;
}

Compilation message (stderr)

roads.cpp: In constructor 'node::node(ll)':
roads.cpp:19:12: warning: 'node::sum' will be initialized after [-Wreorder]
   19 |     ll val,sum;
      |            ^~~
roads.cpp:18:13: warning:   'int node::prior' [-Wreorder]
   18 |     int cnt,prior;
      |             ^~~~~
roads.cpp:22:5: warning:   when initialized here [-Wreorder]
   22 |     node(ll v) : cnt(1), val(v), sum(v), prior(rand()), l(NULL), r(NULL) {}
      |     ^~~~

• 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