Submission #909978

#	Time	Username	Problem	Language	Result	Execution time	Memory
909978		pragmatist	Road Closures (APIO21_roads)	C++17	0 / 100	57 ms	11212 KiB

roads

#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e5 + 7;
const long long INF = (long long)1e18 + 7;
const long long oo = (long long)1e15 + 7;
const int inf = (int)1e9 + 7;

int n, K, deg[N];
vector<int> g[N];
bool used[N];

bool cmp(int i, int j) {
    return deg[i] > deg[j];
}

int ans, old[N];

void dfs(int v, int pr) {
    used[v] = 1;
    assert(deg[v] > K);
    for(auto to : g[v]) {
        if(deg[to] <= K) {
            break;
        }
        if(!used[to] && to != pr && deg[to] > K) {
            dfs(to, v);
        }
    }
    int need = max(0, deg[v]-K);
    ans += need;
    if(deg[v] > K && pr != -1) {
        deg[pr]--;
    }
}

vector<long long> minimum_closure_costs(int _N, vector<int> _U, vector<int> _V, vector<int> _W) {
    n = _N;
    for(int i = 0; i < n-1; ++i) {
        int u = _U[i];
        int v = _V[i];
        int w = _W[i];
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 0; i < n; ++i) {
        deg[i] = (int)g[i].size();
        old[i] = deg[i];
    }
    for(int i = 0; i < n; ++i) {
        sort(g[i].rbegin(), g[i].rend(), cmp);
    }
    vector<long long> po;
    vector<pair<int, int> > o;
    for(int i = 0; i < n; ++i) {
        o.push_back({deg[i], i});
    }
    sort(o.rbegin(), o.rend());
    int tot = 0;
    for(int k = 0; k <  n; ++k) {
        K = k;
        vector<int> bad;
        for(auto [x, y] : o) {
            if(x <= k) {
                break;
            }
            bad.push_back(y);
        }
        ans = 0;
        for(auto x : bad) {
            if(!used[x]) {
                dfs(x, -1);
            }
        }
        for(auto x : bad) {
            deg[x] = old[x];
            used[x] = 0;
        }
        tot += (int)bad.size();
        po.push_back(ans);
    }
    return po;
}

Compilation message (stderr)

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:43:13: warning: unused variable 'w' [-Wunused-variable]
   43 |         int w = _W[i];
      |             ^

• 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