# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
563771 | 2022-05-18T06:03:57 Z | pvpwarrior | Road Closures (APIO21_roads) | C++14 | 2000 ms | 19892 KB |
#include "roads.h" #include <bits/stdc++.h> using namespace std; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define ll long long #define vi std::vector<ll> #define si set<ll> #define INF 100000000 #define pb push_back #define mod 1000000007 std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) { ll n = N; set<pair < ll, ll > > adj[n]; // for (int i = 0; i < n-1; ++i){ // cin >> u[i] >> v[i] >> w[i]; // } // for (int i = 0; i < n; ++i){ // cin >> v[i]; // } // for (int i = 0; i < n; ++i){ // cin >> w[i]; // } for (int i = 0; i < n-1; ++i){ adj[V[i]].insert(make_pair(W[i] , U[i])); adj[U[i]].insert(make_pair(W[i] , V[i])); } // for (int i = 0; i < n; ++i) // { // cout << i << ": "; // for(auto x: adj[i]){ // cout << "(" << x.first << ", " << x.second << "), "; // } // cout << "\n"; // } vi ans(n,0); ll sum = 0; for (int k = n-1; k >= 0; k--){ sum = 0; // cout << k << " :\n"; for (int i = 0; i < n; ++i){ while(adj[i].size() > k){ auto it = adj[i].begin(); pair <ll ,ll > x = *it; sum += x.first; ll in = x.second; auto it2 = adj[in].find(make_pair(x.first, i)); pair <ll ,ll > y = *it2; adj[x.second].erase(it2); // return 0; // cout << x.first << " " << x.second << "\n"; // cout << y.first << " " << y.second << "\n"; adj[i].erase(it); // cout << "\n"; } // cout << "\n"; } // cout << "\n"; if(n-1-k) ans[n-1-k]=ans[n-k-2]; ans[n-1-k] += sum; } // for (int i = n-1; i >= 0; i--){ // cout << ans[i] << " "; // } reverse(ans.begin(), ans.end()); return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 5 ms | 692 KB | Output is correct |
3 | Correct | 6 ms | 724 KB | Output is correct |
4 | Correct | 5 ms | 724 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 4 ms | 564 KB | Output is correct |
9 | Correct | 5 ms | 720 KB | Output is correct |
10 | Correct | 1 ms | 300 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Execution timed out | 2082 ms | 13132 KB | Time limit exceeded |
13 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Execution timed out | 2064 ms | 19020 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Incorrect | 1 ms | 212 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Incorrect | 1 ms | 212 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2093 ms | 19892 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2093 ms | 19892 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 5 ms | 692 KB | Output is correct |
3 | Correct | 6 ms | 724 KB | Output is correct |
4 | Correct | 5 ms | 724 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 4 ms | 564 KB | Output is correct |
9 | Correct | 5 ms | 720 KB | Output is correct |
10 | Correct | 1 ms | 300 KB | Output is correct |
11 | Correct | 1 ms | 212 KB | Output is correct |
12 | Execution timed out | 2082 ms | 13132 KB | Time limit exceeded |
13 | Halted | 0 ms | 0 KB | - |