oj.uz

Submission #413030

# Submission time Handle Problem Language Result Execution time Memory
413030 2021-05-28T06:14:03 Z phathnv Road Closures (APIO21_roads) C++11
0 / 100
 2000 ms 33044 KB 
#include <bits/stdc++.h>
#include "roads.h"
using namespace std;

const int N = 1e5;

int k, deg[N], dp[N][2];
long long sum[N], f[N];
multiset<long long> s[N][2];
vector<pair<int, int>> preAdj[N], adj[N];
bool mark[N], vst[N];

void Add(int u, long long val0, long long val1) {
    val1 = min(val1, val0);
    sum[u] += val0;
    f[u] += val1 - val0;
    s[u][0].insert(val1 - val0);
}

void Del(int u, long long val0, long long val1) {
    val1 = min(val1, val0);
    sum[u] -= val0;
    if (s[u][0].find(val1 - val0) != s[u][0].end()) {
        f[u] -= val1 - val0;
        s[u][0].erase(s[u][0].find(val1 - val0));
    } else {
        s[u][1].erase(s[u][1].find(val1 - val0));
    }
}

void Fix(int u, int sz) {
    while((int) s[u][0].size() > sz) {
        long long x = *s[u][0].rbegin();
        f[u] -= x;
        s[u][0].erase(s[u][0].find(x));
        s[u][1].insert(x);
    }
    while((int) s[u][0].size() < sz && !s[u][1].empty()) {
        long long x = *s[u][1].begin();
        f[u] += x;
        s[u][1].erase(s[u][1].find(x));
        s[u][0].insert(x);
    }
}

void Dfs(int u, int p) {
    vst[u] = 1;
    vector<pair<long long, long long>> vals;
    for(auto e : adj[u]) {
        int v = e.first;
        int w = e.second;
        if (v == p)
            continue;
        Dfs(v, u);
        vals.push_back({dp[v][1] + w, dp[v][0]});
    }
    for(auto p : vals)
        Add(u, p.first, p.second);
    Fix(u, k);
    dp[u][1] = sum[u] + f[u];
    dp[u][0] = sum[u] + (f[u] - *s[u][0].rbegin());
    for(auto p : vals)
        Del(u, p.first, p.second);

}

vector<long long> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
    k = n;
    vector<int> ord(n);
    for(int i = 0; i < n - 1; i++) {
        deg[u[i]]++;
        deg[v[i]]++;
        Add(u[i], w[i], 0);
        Add(v[i], w[i], 0);
        preAdj[u[i]].push_back({v[i], w[i]});
        preAdj[v[i]].push_back({u[i], w[i]});
    }
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](const int &u, const int &v) {
        return deg[u] > deg[v];
    });
    vector<long long> res(n, 0);
    int ptr = 0;
    for(k = n - 1; k >= 1; k--) {
        while(ptr < n && deg[ord[ptr]] > k) {
            int u = ord[ptr++];
            mark[u] = 1;
            for(auto e : preAdj[u]) {
                int v = e.first;
                int w = e.second;
                if (!mark[v])
                    continue;
                Del(u, w, 0);
                Del(v, w, 0);
                adj[u].push_back({v, w});
                adj[v].push_back({u, w});
            }
        }
        memset(vst, 0, sizeof(vst));
        for(int u = 0; u < n; u++)
            if (mark[u] && !vst[u]) {
                Dfs(u, -1);
                res[k] += dp[u][1];
            }
    }
    res[0] = accumulate(w.begin(), w.end(), 0ll);

    return res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Incorrect 25 ms 14796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14500 KB Output is correct
2 Execution timed out 2072 ms 29328 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 9 ms 14484 KB Output is correct
3 Correct 10 ms 14412 KB Output is correct
4 Incorrect 11 ms 14512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 9 ms 14484 KB Output is correct
3 Correct 10 ms 14412 KB Output is correct
4 Incorrect 11 ms 14512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 33044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 33044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Incorrect 25 ms 14796 KB Output isn't correct
3 Halted 0 ms 0 KB -