結果
問題 | No.2642 Don't cut line! |
ユーザー |
|
提出日時 | 2024-02-19 23:19:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 179 ms / 4,000 ms |
コード長 | 2,715 bytes |
コンパイル時間 | 3,483 ms |
コンパイル使用メモリ | 216,032 KB |
最終ジャッジ日時 | 2025-02-19 17:45:19 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll=long long;namespace Lib {struct DSU {vector<int> par, sz;DSU(int n) : par(n), sz(n) {fill(par.begin(), par.end(), -1);fill(sz.begin(), sz.end(), 1);}int leader(int a) {if (par[a] == -1) return a;return par[a] = leader(par[a]);}void merge(int a, int b) {a = leader(a), b = leader(b);if (a == b) return;if (sz[a] > sz[b]) swap(a, b);par[a] = b;sz[b] += sz[a];}bool same(int a, int b) {a = leader(a), b = leader(b);return a == b;}int size(int v) {v = leader(v);return sz[v];}};} // namespace Libint main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N,K;ll C;cin>>N>>K>>C;vector E(K,array<int,4>());for(int i=0;i<K;i++){cin>>E[i][1]>>E[i][2]>>E[i][0]>>E[i][3];--E[i][1],--E[i][2];}sort(E.begin(),E.end());vector tree(N,vector(0,array<int,2>()));Lib::DSU dsu(N);int base=0;for(int i=0;i<K;i++){auto [w,a,b,c]=E[i];if(dsu.same(a,b))continue;tree[a].push_back({b,w});tree[b].push_back({a,w});dsu.merge(a,b);C-=w;base=max(base,c);}if(C<0){cout<<"-1\n";return 0;}constexpr int bit_N=17;vector lca(N,vector(bit_N,-1)),w_max(N,vector(bit_N,0));queue<int>bfs;vector dist(N,(int)1e9);bfs.push(0);dist[0]=0;while(bfs.size()){int v=bfs.front();bfs.pop();for(auto [i,w]:tree[v]){if(dist[i]>dist[v]+1){dist[i]=dist[v]+1;bfs.push(i);lca[i][0]=v;w_max[i][0]=w;}}}for(int j=0;j<bit_N-1;j++){for(int i=0;i<N;i++){if(lca[i][j]==-1)continue;lca[i][j+1]=lca[lca[i][j]][j];w_max[i][j+1]=max(w_max[i][j],w_max[lca[i][j]][j]);}}// for(int i=0;i<N;i++){// cout<<"lca "<<i<<": ";// for(int j=0;j<bit_N;j++)cout<<lca[i][j]<<' ';cout<<'\n';// cout<<"w "<<i<<": ";// for(int j=0;j<bit_N;j++)cout<<w_max[i][j]<<' ';cout<<'\n';// }auto get_max=[&lca,&w_max,&dist](int a,int b){int ret=0,at=dist[a],bt=dist[b];if(at>bt){swap(a,b);swap(at,bt);}for(int i=0;i<bit_N;i++){if((bt-at)>>i&1){ret=max(ret,w_max[b][i]);b=lca[b][i];}}if(a==b){return ret;}for(int i=bit_N-1;i>=0;i--){int ra=lca[a][i],rb=lca[b][i];if(ra!=-1&&ra!=rb){ret=max({ret,w_max[a][i],w_max[b][i]});a=ra,b=rb;}}ret=max({ret,w_max[a][1],w_max[b][1]});return ret;};int ans=base;for(int i=0;i<K;i++){auto [w,a,b,c]=E[i];if(w-get_max(a,b)<=C){ans=max(ans,c);}}cout<<ans<<'\n';}