Submission #1034195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034195		_8_8_	Road Closures (APIO21_roads)	C++17	0 / 100	2099 ms	17360 KiB

roads

#include "roads.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> d,u,v,w;

ll get(int i,int k){
    ll ans = (d[u[i]] > k) + (d[v[i]] > k);
    return ans;
}
ll inf = (int)1e9;
ll cost(int i,int k){
    int _ = get(i,k);
    if(_ ==0) return -1;
    if(_ == 1) return inf + w[i];
    return w[i];
}
const int maxn = (int)1e5 +12;
vector<pair<int,int>> g[maxn];
int vis[maxn];
vector<long long> minimum_closure_costs(int N,vector<int> U,vector<int> V,vector<int> W) {
    u = U;
    v = V;
    w = W;
    vector<int> deg(N,0);
    for(int i = 0;i < N - 1;i++){
        deg[U[i]]++;
        deg[V[i]]++;
        g[u[i]].push_back({v[i],i});
        g[v[i]].push_back({u[i],i});
    }
    vector<ll> ans;
    int timer = 0;
    for(int i = 0;i < N;i++){
        timer++;
        d = deg;
        set<pair<ll,int>> st;
        ll res = 0;
        for(int j = 0;j < N - 1;j++){
            ll A = cost(j,i);
            if(A == -1) continue;
            st.insert({A,j});
        }
        while(!st.empty()){
            auto [c,j] = (*st.begin());
            vis[j] = timer;
            assert(c != -1);
            res += w[j];
            st.erase({c,j});
            int x = u[j],y = v[j];
            d[x]--;d[y]--;
            for(auto [to,id]:g[x]){
                if(vis[id] == timer) continue;
                if(to == y) continue;
                d[x]++;
                st.erase({cost(id,i),id});
                d[x]--;
                ll A = cost(id,i);
                if(A != -1){
                    st.insert({A,id});
                }
            }
            for(auto [to,id]:g[y]){
                if(vis[id] == timer) continue;
                if(to == x) continue;
                d[y]++;
                st.erase({cost(id,i),id});
                d[y]--;
                ll A = cost(id,i);
                if(A != -1){
                    st.insert({A,id});
                }
            }
        }
        if((int)ans.size()){
            assert(res <= ans.back());
        }
        ans.push_back(res);
    }
    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