# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
981354 | Jawad_Akbar_JJ | 도로 폐쇄 (APIO21_roads) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include "roads.h"
using namespace std;
#define ll long long
const int N = 1e5 + 10;
vector<pair<int,int>> nei[N];
vector<ll> sub1(int n,vector<int> W){
sort(rbegin(W),rend(W));
vector<ll> v;
v.push_back(0);
for (int i : W)
v[0] += i;
for (int i : W)
v.push_back(v.back() - i);
return v;
}
vector<ll> sub1(int n,vector<int> W){
ll t = W[0];
ll nt = 0;
vector<ll> v(n,0);
v[0] += W[0];
for (int i=1;i<n-1;i++){
ll a = t;
t = min(t,nt) + W[i];
nt = a;
v[0] += W[i];
}
v[1] = min(t,nt);
return v;
}
int minimum_closure_costs(int n,vector<int> U,vector<int> V,vector<int> W){
long long sum = 0,sum2 = 0,sum3 = 0;
for (int i=0;i<n-1;i++)
sum += U[i],sum2 += W[i],sum3 += (U[i] == i);
if (sum == 0)
return sub1(n,W);
if (sum2 == n-1)
return sub5(n,U,V);
if (sum3 == n-1)
return sub2(n,W);
}