oj.uz

Submission #883001

# Submission time Handle Problem Language Result Execution time Memory
883001 2023-12-04T11:36:38 Z dimashhh Road Closures (APIO21_roads) C++17
0 / 100
 2000 ms 23800 KB 
#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,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,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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Execution timed out 2084 ms 3196 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 476 ms 20920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 792 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 792 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Execution timed out 2084 ms 3196 KB Time limit exceeded
3 Halted 0 ms 0 KB -