제출 #984470

#제출 시각아이디문제언어결과실행 시간메모리
984470Marcus도로 폐쇄 (APIO21_roads)C++17
0 / 100
40 ms7880 KiB
#include "roads.h" #include <vector> #include <bits/stdc++.h> using namespace std; #define ll long long const ll N1 = 1e5; vector<int> chain(N1); vector<int> portion(N1, 1); int find(int x) { while (x != chain[x]) x = chain[x]; return x; } bool same(int a, int b) { return find(a) == find(b); } void unite(int a, int b) { a = find(a); b = find(b); if (portion[a] < portion[b]) swap(a,b); portion[a] += portion[b]; chain[b] = a; } std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) { vector<tuple<ll, ll, ll>> edge(N-1); for (int i=0; i<N-1; i++) { edge[i] = {W[i], U[i], V[i]}; } sort(edge.begin(), edge.end()); reverse(edge.begin(), edge.end()); for (int i=0; i<N; i++) {chain[i] = i;} ll reduction = 0; ll total = 0; for (auto e: edge) { ll c = get<0>(e); ll u = get<1>(e); ll v = get<2>(e); total += c; if (portion[find(u)] == 1 && portion[find(v)] == 1) {unite(u, v); reduction += c;} } //cout<<"\n"; vector<ll> answer = {total, total - reduction}; for (int i=0; i<N-2; i++) {answer.push_back(0);} return answer; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...