結果
問題 | No.2642 Don't cut line! |
ユーザー | otoshigo |
提出日時 | 2024-02-20 14:47:00 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,962 bytes |
コンパイル時間 | 1,416 ms |
コンパイル使用メモリ | 106,432 KB |
実行使用メモリ | 20,588 KB |
最終ジャッジ日時 | 2024-09-29 03:43:24 |
合計ジャッジ時間 | 6,486 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | AC | 64 ms
11,084 KB |
testcase_07 | AC | 61 ms
10,396 KB |
testcase_08 | AC | 60 ms
10,712 KB |
testcase_09 | AC | 61 ms
10,096 KB |
testcase_10 | AC | 61 ms
10,076 KB |
testcase_11 | AC | 60 ms
10,652 KB |
testcase_12 | AC | 61 ms
10,716 KB |
testcase_13 | AC | 60 ms
10,596 KB |
testcase_14 | AC | 61 ms
10,552 KB |
testcase_15 | AC | 62 ms
10,800 KB |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | AC | 54 ms
11,116 KB |
testcase_22 | AC | 62 ms
11,112 KB |
testcase_23 | RE | - |
testcase_24 | AC | 67 ms
20,588 KB |
testcase_25 | AC | 63 ms
18,788 KB |
testcase_26 | AC | 68 ms
12,432 KB |
testcase_27 | RE | - |
testcase_28 | RE | - |
testcase_29 | AC | 69 ms
14,256 KB |
testcase_30 | AC | 62 ms
17,252 KB |
testcase_31 | RE | - |
testcase_32 | AC | 64 ms
16,812 KB |
testcase_33 | AC | 2 ms
6,816 KB |
testcase_34 | AC | 2 ms
6,816 KB |
testcase_35 | AC | 2 ms
6,816 KB |
ソースコード
#include<iostream> #include<algorithm> #include<vector> #include<tuple> using namespace std; using ll=long long; #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;} template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;} struct UnionFind { private: vector<int> par, siz; public: UnionFind(int n) : par(n, -1), siz(n, 1) {} int find(int x) { if (par[x] == -1) return x; else { par[x] = find(par[x]); return par[x]; } } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return siz[find(x)]; } bool merge(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; return true; } }; const ll INF=1LL<<60; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N,K,C; cin>>N>>K>>C; vector<tuple<ll,int,int,int>>vt; for(int i=0;i<K;i++){ int u,v,p; ll w; cin>>u>>v>>w>>p; u--; v--; vt.push_back(make_tuple(w,u,v,p)); } UnionFind uf(N); ll cost=0; int ans=0; vector<tuple<ll,int,int,int>>vt2; vector<vector<pair<int,ll>>>G(N); sort(all(vt)); for(auto[w,u,v,p]:vt){ if(uf.same(u,v)){ vt2.push_back(make_tuple(w,u,v,p)); }else{ uf.merge(u,v); cost+=w; chmax(ans,p); G[u].push_back(make_pair(v,w)); G[v].push_back(make_pair(u,w)); } } if(cost>C){ cout<<-1<<"\n"; return 0; } vector<int>D(N); vector P(20,vector<int>(N,-1)); vector M(20,vector<ll>(N,-INF)); auto dfs=[&](auto dfs,int x,int p,ll w)-> void { P[0][x]=p; M[0][x]=w; for(int i=1;i<20;i++){ if(P[i-1][x]==-1)break; P[i][x]=P[i-1][P[i-1][x]]; M[i][x]=max(M[i-1][x],M[i-1][P[i-1][x]]); } for(auto[i,e]:G[x]){ if(i==p)continue; D[i]=D[x]+1; dfs(dfs,i,x,e); } }; dfs(dfs,0,-1,-INF); for(auto[w,u,v,p]:vt2){ if(D[u]>D[v])swap(u,v); ll mx=-INF; for(int i=0;i<20;i++){ if((D[v]-D[u])>>i&1){ chmax(mx,M[i][v]); v=P[i][v]; } } if(u!=v){ for(int i=19;i>=0;i--){ if(P[i][u]!=P[i][v]){ chmax(mx,max(M[i][u],M[i][v])); u=P[i][u]; v=P[i][v]; } } } if(cost-mx+w<=C)chmax(ans,p); } cout<<ans<<"\n"; } /* 4 4 101 1 2 1 1 1 3 1 3 3 4 1 2 2 4 100 4 4 6 5 1 2 3 1 1 3 1 2 1 4 2 3 2 3 2 3 2 4 3 5 3 4 2 2 */