結果

問題 No.2642 Don't cut line!
ユーザー ponjuice
提出日時 2024-02-15 17:38:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 224 ms / 4,000 ms
コード長 3,130 bytes
コンパイル時間 2,499 ms
コンパイル使用メモリ 213,312 KB
最終ジャッジ日時 2025-02-19 13:14:47
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct UF{
int n;
vector<int> par;
UF(int _n) : n(_n), par(_n, -1) {}
int root(int p){
if(par[p] < 0) return p;
return par[p] = root(par[p]);
}
bool same(int l, int r){
return root(l) == root(r);
}
void merge(int l, int r){
if(same(l, r)) return;
l = root(l);
r = root(r);
if(par[l] > par[r]) swap(l, r);
par[l] += par[r];
par[r] = l;
}
};
int main(){
ll n, m, c;
cin >> n >> m >> c;
vector<pair<int, int>> edges(m);
vector<ll> w(m);
vector<ll> p(m);
for(int i = 0; i < m; i++){
cin >> edges[i].first >> edges[i].second >> w[i] >> p[i];
edges[i].first--, edges[i].second--;
}
vector<int> Kruskal(m);
iota(Kruskal.begin(), Kruskal.end(), 0);
sort(Kruskal.begin(), Kruskal.end(), [&](int l,int r){
return w[l] < w[r];
});
UF uf(n);
vector<vector<pair<int,ll>>> graph(n);
ll W = 0, P = 0;
for(int i = 0; i < m; i++){
if(!uf.same(edges[Kruskal[i]].first, edges[Kruskal[i]].second)){
uf.merge(edges[Kruskal[i]].first, edges[Kruskal[i]].second);
graph[edges[Kruskal[i]].first].emplace_back(edges[Kruskal[i]].second, w[Kruskal[i]]);
graph[edges[Kruskal[i]].second].emplace_back(edges[Kruskal[i]].first, w[Kruskal[i]]);
W += w[Kruskal[i]];
P = max(P, p[Kruskal[i]]);
}
}
if(W > c){
cout << -1 << endl;
return 0;
}
vector<vector<pair<int,ll>>> db(10, vector<pair<int,ll>>(n, {-1, 0}));
vector<int> depth(n, 0);
auto dfs = [&](auto&& dfs, int nw, int par)->void {
for(auto [to, cost] : graph[nw]){
if(to != par){
depth[to] = depth[nw] + 1;
db[0][to] = {nw, cost};
dfs(dfs, to, nw);
}
}
};
dfs(dfs, 0, -1);
for(int i = 1; i < 10; i++){
for(int j = 0; j < n; j++){
if(db[i-1][j].first != -1){
db[i][j] = {db[i-1][db[i-1][j].first].first, max(db[i-1][db[i-1][j].first].second, db[i-1][j].second)};
}
}
}
for(int i = 0; i < m; i++){
if(p[i] <= P)continue;
auto[u, v] = edges[i];
if(depth[u] < depth[v]) swap(u, v);
ll mxW = 0;
for(int i = 9; i >= 0; i--){
if(db[i][u].first != -1 && depth[db[i][u].first] >= depth[v]){
mxW = max(mxW, db[i][u].second);
u = db[i][u].first;
}
}
if(u != v){
for(int i = 9; i > 0; i--){
if(db[i][u].first != db[i][v].first){
mxW = max(mxW, db[i][u].second);
mxW = max(mxW, db[i][v].second);
u = db[i][u].first;
v = db[i][v].first;
}
}
mxW = max(mxW, db[0][u].second);
mxW = max(mxW, db[0][v].second);
}
if(W - mxW + w[i] <= c) P = p[i];
}
cout << P << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0