QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #413411 | #1490. Road Closures | stegatxins0# | 0 | 3ms | 4016kb | C++20 | 1.6kb | 2024-05-17 14:58:38 | 2024-05-17 14:58:39 |
answer
#include <bits/stdc++.h>
#include "roads.h"
using namespace std;
using ll = long long;
#ifdef DEBUG
#include "debug.cpp"
#else
#define dbg(...)
#define dbgarr(...)
#endif
// given nodes, construct a tree such that the tree has maximum weight and each node is connected
// to at most k nodes
// greedy aka removing road with most weight doesnt work
struct Edge{
int u, v, w;
} G;
bool visited[2005];
int N;
bool cmp(const Edge &x, const Edge &y){
return x.w > y.w;
}
ll visit(int u, int k, vector<Edge>&G){
if(k == 0)return 0;
int deg[N], mx=G[u].w;
memset(deg,0,sizeof(deg));
deg[G[u].u]++;
deg[G[u].v]++;
for(int i=0; i<N-1; i++){
if(i == u)continue;
if(deg[G[i].u]+1 <= k && deg[G[i].v]+1<=k){
// can add
deg[G[i].u]++;
deg[G[i].v]++;
visited[i] = 1;
mx += G[i].w;
}
}
return mx;
}
std::vector<long long> minimum_closure_costs(int _N, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
N = _N;
vector<Edge> G;
ll sum=0;
vector<ll> ans(N,0);
for(int i=0; i<N-1; i++){
sum += W[i];
G.push_back({U[i], V[i], W[i]});
}
sort(G.begin(), G.end(), cmp);
memset(visited,0,sizeof(visited));
ll curans = 0;
// choose max k edge
for(int i=0; i<N-1; i++){
if(!visited[i]){
ll cur = visit(i, 1, G);
curans = max(curans, cur);
}
}
ans[1] = sum - curans;
ans[0] = sum;
return ans;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 3860kb
input:
c10234cabdfd6eae47773fb6f163e0350fc797e1 2000 0 559 717769868 0 237 766447943 0 122 517523402 0 1779 560381127 0 1477 566064983 0 67 303410673 0 1869 605544497 0 1769 774963386 0 457 469996896 0 201 995323973 0 1694 885366346 0 1547 362843462 0 55 947026157 0 1302 448837561 0 733 673028958 0 1139 65...
output:
064bde9ff69ddc34b3b45c2d26d58873d85290d3 OK 1239932930636 1238933034699 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 3rd lines differ - expected: '1239932930636 1238933034699 12...752918397 501659798 250746454 0', found: '1239932930636 1238933034699 0 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'
Subtask #2:
score: 0
Runtime Error
Test #19:
score: 7
Accepted
time: 1ms
memory: 3772kb
input:
c10234cabdfd6eae47773fb6f163e0350fc797e1 2 0 1 4
output:
064bde9ff69ddc34b3b45c2d26d58873d85290d3 OK 4 0
result:
ok 3 lines
Test #20:
score: 0
Runtime Error
input:
c10234cabdfd6eae47773fb6f163e0350fc797e1 82978 0 1 687749865 1 2 811016969 2 3 502155590 3 4 930576294 4 5 879987412 5 6 883450944 6 7 975772046 7 8 739249697 8 9 954502114 9 10 962223056 10 11 562948742 11 12 933819577 12 13 614418299 13 14 724040317 14 15 798630312 15 16 583709944 16 17 634442427 ...
output:
Unauthorized output
result:
Subtask #3:
score: 0
Wrong Answer
Test #34:
score: 14
Accepted
time: 1ms
memory: 4016kb
input:
c10234cabdfd6eae47773fb6f163e0350fc797e1 2 0 1 4
output:
064bde9ff69ddc34b3b45c2d26d58873d85290d3 OK 4 0
result:
ok 3 lines
Test #35:
score: 0
Wrong Answer
time: 1ms
memory: 3748kb
input:
c10234cabdfd6eae47773fb6f163e0350fc797e1 5 0 1 1 0 2 4 0 3 3 2 4 2
output:
064bde9ff69ddc34b3b45c2d26d58873d85290d3 OK 10 5 0 0 0
result:
wrong answer 3rd lines differ - expected: '10 5 1 0 0', found: '10 5 0 0 0'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Runtime Error
Test #79:
score: 0
Runtime Error
input:
c10234cabdfd6eae47773fb6f163e0350fc797e1 96680 81008 32770 1 53103 75975 1 38090 49649 1 35805 25778 1 50058 68261 1 52213 58881 1 52672 34310 1 1080 42408 1 32306 82599 1 73623 7340 1 87691 42161 1 78365 96557 1 78654 88488 1 5875 25925 1 23217 85743 1 18698 42579 1 90401 84720 1 45973 91271 1 5282...
output:
Unauthorized output
result:
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%