이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//oh god why
#include "roads.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
struct DS {
ll tot, dif, uval;
// least = best to edge
bool operator<(const DS& ot) const {
return dif > ot.dif;
}
};
vector<pl> pe;
vector<vector<ii> > g;
// vertex, edge color
vector<map<int,vector<DS>>> dpt;
vector<map<int,int> > degr;
vi wex;
void dfb(int u, int p, int col, int st, int deg) {
int kv = degr[u][col]-(1-st)-deg;
int sus = 0;
int kt = 0;
for(const auto& eg: dpt[u][col]) {
int v = eg.uval;
if(kt < kv && eg.dif > 0) {
dfb(v,u,col,0,deg);
sus++;
} else {
wex[v] |= deg;
dfb(v,u,col,1,deg);
}
kt++;
}
if(!st) {
sus++;
}
if(sus < kt+1) {
degr[u][col|deg] = degr[u][col]-sus;
}
if(sus > 0) {
degr[u][col] = degr[u][col]-deg;
}
}
void dfa(int u, int p, int deg) {
for(int i=0;i<g[u].size();i++) {
int v = g[u][i].first;
if(v == p) {continue;}
dfa(v,u,deg);
}
dpt[u][wex[u]];
for(const auto& colp: dpt[u]) {
int col = colp.first;
auto& subs = dpt[u][col];
sort(subs.begin(),subs.end());
pl res = {0,pe[u].second};
int kv = degr[u][col]-deg;
int kt = 0;
for(const auto& eg: subs) {
res.first += eg.tot;
res.second += eg.tot;
if(kt < kv) {
ll dv = max(eg.dif,0LL);
res.first += dv;
if(kt < kv-1) {
res.second += dv;
}
}
kt++;
}
if(u != p && col == wex[u]) {
dpt[p][col].push_back({res.first,res.second-res.first,u});
} else {
dfb(u,p,col,1,deg);
}
}
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
ll sus = 0;
pe.resize(N);
g.resize(N);
wex.resize(N);
int M = U.size();
for(int i=0;i<M;i++) {
int u = U[i];
int v = V[i];
int c = W[i];
g[u].emplace_back(v,c);
g[v].emplace_back(u,c);
sus += c;
}
int h = 0;
while(1<<h < N) {
h++;
}
vi ord;
{
stack<ii> st;
st.emplace(0,0);
ord.push_back(0);
while(!st.empty()) {
int u = st.top().first;
ord.push_back(u);
int p = st.top().second;
st.pop();
for(int i=0;i<g[u].size();i++) {
int v = g[u][i].first;
if(v == p) {continue;}
int c = g[u][i].second;
st.emplace(v,u);
pe[v] = {u,c};
}
}
}
degr.resize(N);
for(int i=0;i<N;i++) {
degr[i][0] = 1<<(h);
}
for(int db=h-1;db>=0;db--) {
dpt.assign(N,map<int,vector<DS>>());
dfa(0,0,1<<db);
}
vector<ll> ans(N);
for(int i=1;i<N;i++) {
ans[wex[i]+1] += pe[i].second;
}
for(int i=1;i<ans.size();i++) {
ans[i] += ans[i-1];
}
for(int i=0;i<ans.size();i++) {
ans[i] = sus-ans[i];
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
roads.cpp: In function 'void dfa(int, int, int)':
roads.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i=0;i<g[u].size();i++) {
| ~^~~~~~~~~~~~
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:116:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int i=0;i<g[u].size();i++) {
| ~^~~~~~~~~~~~
roads.cpp:137:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int i=1;i<ans.size();i++) {
| ~^~~~~~~~~~~
roads.cpp:140:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(int i=0;i<ans.size();i++) {
| ~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |