Submission #883004

#	Time	Username	Problem	Language	Result	Execution time	Memory
883004		dimashhh	Road Closures (APIO21_roads)	C++17	0 / 100	2086 ms	22504 KiB

roads

#include "roads.h"

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 12;
typedef long long ll;
int s[maxn],res[maxn];
set<pair<ll,pair<ll,ll>>> st;
set<pair<ll,pair<ll,ll>>> st1;
vector<pair<int,pair<int,int>>> g[maxn];
void del_v(int v){
    s[v]--;
    for(auto [to,f]:g[v]){
        int w = f.first,i = f.second;
        st.erase({min(s[v] + 1,s[to]),{-w,i}});
        st1.erase({max(s[v] + 1,s[to]),{-w,i}});
        st.insert({min(s[v],s[to]),{-w,i}});
        st1.insert({max(s[v],s[to]),{-w,i}});
    }
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> u,
                                             std::vector<int> v,
                                             std::vector<int> w)
{
    vector<ll> res;
    ll ans = 0;
    for(int i = 0;i < N - 1;i++){
        s[u[i]]++;
        s[v[i]]++;
        g[u[i]].push_back({v[i],{w[i],i}});
        g[v[i]].push_back({u[i],{w[i],i}});
        ans += w[i];
    }
    ll sm = ans;
    for(int i = 0;i < N -1 ;i++){
        st.insert({min(s[u[i]],s[v[i]]),{-w[i],i}});
        st1.insert({max(s[u[i]],s[v[i]]),{-w[i],i}});
        // cout << max(s[u[i]],s[v[i]]) << ' ' << w[i] << '\n';
    }

    for(int j = N - 1;j >= 0;j--){
        while(!st.empty()){
            auto [x,y] = *st.rbegin();
            if(x <= j) break;
            del_v(u[y.second]);
            del_v(v[y.second]);
            ans += y.first;
            st.erase({x -1,y});
        }
        while(!st1.empty()){
            auto [x,y] = *st1.rbegin();
            if(max(s[u[y.second]],s[v[y.second]]) <= j) break;            
            del_v(u[y.second]);
            ans += y.first;
            del_v(v[y.second]);
            st1.erase({x - 1,y});
        }
        res.push_back(sm - ans);
    }
    reverse(res.begin(),res.end());
    return res;
}
// int main()
// {
//     int N;
//     assert(1 == scanf("%d", &N));

//     std::vector<int> U(N - 1), V(N - 1), W(N - 1);
//     for (int i = 0; i < N - 1; ++i)
//     {
//         assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
//     }

//     std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W);
//     for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i)
//     {
//         if (i > 0)
//         {
//             printf(" ");
//         }
//         printf("%lld", closure_costs[i]);
//     }
//     printf("\n");
//     return 0;
// }

• 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