結果
問題 | No.2642 Don't cut line! |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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;}