oj.uz

Submission #552201

# Submission time Handle Problem Language Result Execution time Memory
552201 2022-04-22T17:18:08 Z marsxiang5902 Road Closures (APIO21_roads) C++17
7 / 100
 2000 ms 29516 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MN = 1e5+5;

int N, sz[MN]; vector<pair<int,int>> adjl[MN]; ll ans[MN]; vector<ll> diffs[MN];

struct KMin{
    multiset<ll> st; int k;
    void init(int _k){ st.clear(); k = _k; }
    void insert(ll x){ st.insert(x); }
    void erase(ll x){ st.erase(st.find(x)); }
    void decK(){ assert(k--); }
    ll query(){
        assert(st.size() >= k);
        ll ret = 0;
        int i = 0;
        for(auto it = st.begin(); i < k; i++, it++)
            ret += *it;
        return ret;
    }
} kMin;

void dfs(int u){
    sort(adjl[u].begin(), adjl[u].end(), [](pair<int,int> lhs, pair<int,int> rhs){
        return sz[lhs.first] > sz[rhs.first];
    });
    for(auto [v, w]: adjl[u]){
        adjl[v].erase(find(adjl[v].begin(), adjl[v].end(), pair(u, w)));
        dfs(v);
    }
    diffs[u].resize(sz[u]);
    kMin.init(sz[u] - 1);
    for(auto [v, w]: adjl[u])
        kMin.insert(w);
    for(int k = 1; k < sz[u]; k++){
        for(auto [v, w]: adjl[u]){
            if(sz[v] <= k) break;
            kMin.erase(w);
            if(diffs[v][k] > w)
                ans[k] += w - diffs[v][k];
            kMin.insert(max(0LL, w - diffs[v][k]));
        }
        assert(kMin.k == sz[u] - k);
        ll res1 = kMin.query();
        kMin.decK();
        ll res2 = kMin.query();
        ans[k] += res1;
        diffs[u][k] = res1 - res2;
        for(auto [v, w]: adjl[u]){
            if(sz[v] <= k) break;
            kMin.insert(w);
            kMin.erase(max(0LL, w - diffs[v][k]));
        }
    }
}

vector<ll> minimum_closure_costs(int _N, vector<int> us, vector<int> vs, 
    vector<int> ws){
    N = _N;
    for(int i = 0, u, v, w; i < N-1; i++){
        u = us[i]; v = vs[i]; w = ws[i];
        adjl[u].emplace_back(v, w);
        adjl[v].emplace_back(u, w);
    }
    for(int i = 0; i < N; i++)
        sz[i] = adjl[i].size();
    ++sz[0];
    dfs(0);
    ans[0] = accumulate(ws.begin(), ws.end(), 0LL);
    for(int k = 1; k < sz[0]; k++)
        ans[k] -= diffs[0][k];
    return vector<ll>(ans, ans+N);
}

#ifdef LOCAL_PROJECT
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int N; cin >> N;
    vector<int> us(N-1), vs(N-1), ws(N-1);
    for(int i = 0; i < N-1; i++)
        cin >> us[i] >> vs[i] >> ws[i];
    vector<ll> ans = minimum_closure_costs(N, us, vs, ws);
    for(int i = 0; i < N; i++)
        printf("%d%c", ans[i], " \n"[i==N-1]);

    return 0;
}
#endif

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from roads.cpp:1:
roads.cpp: In member function 'll KMin::query()':
roads.cpp:16:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |         assert(st.size() >= k);
      |                ~~~~~~~~~~^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 37 ms 5296 KB Output is correct
3 Correct 41 ms 5312 KB Output is correct
4 Correct 25 ms 5324 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 27 ms 5272 KB Output is correct
9 Correct 32 ms 5324 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Execution timed out 2094 ms 14192 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 68 ms 23440 KB Output is correct
3 Correct 84 ms 27856 KB Output is correct
4 Correct 99 ms 29332 KB Output is correct
5 Correct 79 ms 29516 KB Output is correct
6 Correct 5 ms 5332 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 4 ms 5400 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 46 ms 19156 KB Output is correct
13 Correct 68 ms 28568 KB Output is correct
14 Correct 3 ms 5008 KB Output is correct
15 Correct 65 ms 26280 KB Output is correct
16 Correct 84 ms 28568 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 15108 KB Output is correct
2 Correct 98 ms 14972 KB Output is correct
3 Correct 256 ms 16768 KB Output is correct
4 Correct 101 ms 15360 KB Output is correct
5 Correct 269 ms 16880 KB Output is correct
6 Correct 1081 ms 16576 KB Output is correct
7 Correct 197 ms 16000 KB Output is correct
8 Execution timed out 2083 ms 19144 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 15108 KB Output is correct
2 Correct 98 ms 14972 KB Output is correct
3 Correct 256 ms 16768 KB Output is correct
4 Correct 101 ms 15360 KB Output is correct
5 Correct 269 ms 16880 KB Output is correct
6 Correct 1081 ms 16576 KB Output is correct
7 Correct 197 ms 16000 KB Output is correct
8 Execution timed out 2083 ms 19144 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 37 ms 5296 KB Output is correct
3 Correct 41 ms 5312 KB Output is correct
4 Correct 25 ms 5324 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 27 ms 5272 KB Output is correct
9 Correct 32 ms 5324 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Execution timed out 2094 ms 14192 KB Time limit exceeded
13 Halted 0 ms 0 KB -