oj.uz

Submission #552182

# Submission time Handle Problem Language Result Execution time Memory
552182 2022-04-22T15:34:01 Z marsxiang5902 Road Closures (APIO21_roads) C++17
0 / 100
 2000 ms 25292 KB 
#include <bits/stdc++.h>
using namespace std;

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

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

struct KMin{
    multiset<ll> st; int k;
    void init(int _k){ k = _k; st.clear(); }
    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);
            kMin.insert(w - diffs[v][k]);
        }
        assert(kMin.k == sz[u] - k);
        ll res1 = kMin.query();
        kMin.decK();
        assert(kMin.k == sz[u] - 1 - k);
        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(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] + 1; v = vs[i] + 1; w = ws[i];
        adjl[u].emplace_back(v, w);
        adjl[v].emplace_back(u, w);
    }
    for(int i = 1; i <= N; i++)
        sz[i] = adjl[i].size();
    ++sz[1];
    dfs(1);
    ans[0] = accumulate(ws.begin(), ws.end(), 0LL);
    for(int i = 1; i < sz[1]; i++)
        ans[i] -= diffs[1][i];
    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 33 ms 5324 KB Output is correct
3 Correct 39 ms 5344 KB Output is correct
4 Correct 22 ms 5344 KB Output is correct
5 Correct 4 ms 5008 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 4 ms 5048 KB Output is correct
8 Correct 25 ms 5272 KB Output is correct
9 Correct 33 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 2056 ms 14548 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5004 KB Output is correct
2 Incorrect 67 ms 25292 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5008 KB Output is correct
2 Correct 3 ms 5004 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 5008 KB Output is correct
2 Correct 3 ms 5004 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 142 ms 16332 KB Output is correct
2 Correct 106 ms 16044 KB Output is correct
3 Correct 230 ms 17812 KB Output is correct
4 Correct 95 ms 16604 KB Output is correct
5 Correct 246 ms 17868 KB Output is correct
6 Correct 1155 ms 17428 KB Output is correct
7 Correct 219 ms 17072 KB Output is correct
8 Execution timed out 2066 ms 20132 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 16332 KB Output is correct
2 Correct 106 ms 16044 KB Output is correct
3 Correct 230 ms 17812 KB Output is correct
4 Correct 95 ms 16604 KB Output is correct
5 Correct 246 ms 17868 KB Output is correct
6 Correct 1155 ms 17428 KB Output is correct
7 Correct 219 ms 17072 KB Output is correct
8 Execution timed out 2066 ms 20132 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 33 ms 5324 KB Output is correct
3 Correct 39 ms 5344 KB Output is correct
4 Correct 22 ms 5344 KB Output is correct
5 Correct 4 ms 5008 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 4 ms 5048 KB Output is correct
8 Correct 25 ms 5272 KB Output is correct
9 Correct 33 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 2056 ms 14548 KB Time limit exceeded
13 Halted 0 ms 0 KB -