結果

問題 No.2642 Don't cut line!
ユーザー Nzt3
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#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 Lib
int 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';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0