結果
問題 | No.2642 Don't cut line! |
ユーザー | Taiki0715 |
提出日時 | 2024-02-19 23:11:14 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 234 ms / 4,000 ms |
コード長 | 6,018 bytes |
コンパイル時間 | 6,619 ms |
コンパイル使用メモリ | 185,192 KB |
実行使用メモリ | 50,072 KB |
最終ジャッジ日時 | 2024-09-29 03:39:02 |
合計ジャッジ時間 | 12,207 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;template<int mod>istream &operator>>(istream &is,static_modint<mod> &a){long long b;is>>b;a=b;return is;}istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;}#endif#ifdef LOCAL#include "debug.h"#else#define debug(...) static_cast<void>(0)#define debugg(...) static_cast<void>(0)template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;}#endifusing ll=long long;using ull=unsigned long long;using P=pair<ll,ll>;template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>;template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);}template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);}template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;}template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;}template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;}template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;}template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;}#define reps(i,a,n) for(int i=(a);i<(n);i++)#define rep(i,n) reps(i,0,n)#define all(x) x.begin(),x.end()#define pcnt(x) __builtin_popcountll(x)ll myceil(ll a,ll b){return (a+b-1)/b;}template<typename T,size_t n,size_t id=0>auto vec(const int (&d)[n],const T &init=T()){if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init));else return init;}void SOLVE();int main(){ios::sync_with_stdio(false);cin.tie(nullptr);#ifdef LOCALclock_t start=clock();#endifint testcase=1;//cin>>testcase;for(int i=0;i<testcase;i++){SOLVE();}#ifdef LOCALcerr<<"time:";cerr<<(clock()-start)/1000;cerr<<"ms\n";#endif}struct HeavyLightDecomposition{int n;vector<vector<int>>to;int root;vector<int>par,pathtop,in,out,dep;vector<int>sub;private:void st_dfs(int x,int p){par[x]=p;sub[x]=1;for(auto &i:to[x]){if(i==p){if(i==to[x].back())break;else swap(i,to[x].back());}st_dfs(i,x);sub[x]+=sub[i];if(sub[i]>sub[to[x][0]]){swap(i,to[x][0]);}}}void hld_dfs(int x,int p,int &id){in[x]=id++;for(auto i:to[x])if(i!=p){dep[i]=dep[x]+1;pathtop[i]=(i==to[x][0]?pathtop[x]:i);hld_dfs(i,x,id);}out[x]=id;}public:HeavyLightDecomposition(int n,int root=0):n(n),to(n),sub(n),par(n),in(n),out(n),root(root),pathtop(n),dep(n),g(n){}void add_edge(int u,int v){to[u].emplace_back(v);to[v].emplace_back(u);}void build(){dep[root]=0;st_dfs(root,-1);pathtop[root]=root;int id=0;hld_dfs(root,-1,id);}inline int get(int x)const{return in[x];}int lca(int u,int v)const{int pu=pathtop[u],pv=pathtop[v];while(pathtop[u]!=pathtop[v]){if(in[pu]>in[pv])u=par[pu],pu=pathtop[u];else v=par[pv],pv=pathtop[v];}return (in[u]>in[v]?v:u);}void subtree_query(int u ,const function<void(int,int)> &f){f(in[u],out[u]);}void path_query(int u,int v,const function<void(int,int)>&f){int pu=pathtop[u],pv=pathtop[v];while(pathtop[u]!=pathtop[v]){if(in[u]>in[v])f(in[pu],in[u]+1),u=par[pu],pu=pathtop[u];else f(in[pv],in[v]+1),v=par[pv],pv=pathtop[v];}if(in[u]>in[v])swap(u,v);f(in[u],in[v]+1);}void noncommutative_path_query(int u,int v,const function<void(int,int)>&f){int l=lca(u,v);while(pathtop[u]!=pathtop[l]){f(in[u]+1,in[pathtop[u]]);u=par[pathtop[u]];}if(u!=l)f(in[u]+1,in[l]+1);f(in[l],in[l]+1);if(v==l)return;vector<pair<int,int>>query;while(true){if(pathtop[l]==pathtop[v]){query.emplace_back(in[l]+1,in[v]+1);break;}query.emplace_back(in[pathtop[v]],in[v]+1);v=par[pathtop[v]];}reverse(all(query));for(auto [i,j]:query)f(i,j);}vector<vector<int>>g;int auxiliary_tree(vector<int>v){sort(all(v),[&](int x,int y){return in[x]<in[y];});v.reserve(v.size()*2-1);int vs=v.size();reps(i,1,vs)v.push_back(lca(v[i-1],v[i]));sort(all(v),[&](int x,int y){return in[x]<in[y];});v.erase(unique(all(v)),v.end());rep(i,v.size())g[v[i]].clear();stack<int>st;rep(i,v.size()){while(!st.empty()&&out[st.top()]<=in[v[i]])st.pop();if(!st.empty()){g[st.top()].push_back(v[i]);g[v[i]].push_back(st.top());}st.push(v[i]);}while(st.size()>1)st.pop();return st.top();}};P op(P x,P y){if(x.first!=y.first)return max(x,y);return min(x,y);}P e(){return {-1,0};}void SOLVE(){int n,m;ll c;cin>>n>>m>>c;vector<int>u(m),v(m),w(m);vector<ll>p(m);rep(i,m){cin>>u[i]>>v[i]>>w[i]>>p[i];u[i]--,v[i]--;}vector<int>id(m);iota(all(id),0);sort(all(id),[&](int x,int y){return w[x]<w[y];});HeavyLightDecomposition hld(n*2-1);int idx=n;ll cost=0,ur=0;dsu uf(n);vector<bool>used(m,false);for(int i:id){if(uf.same(u[i],v[i]))continue;uf.merge(u[i],v[i]);hld.add_edge(u[i],idx);hld.add_edge(v[i],idx);idx++;cost+=w[i];chmax(ur,p[i]);used[i]=true;}segtree<P,op,e>seg(n*2-1);idx=n;hld.build();for(int i:id){if(used[i]){int j=hld.get(idx);seg.set(j,{w[i],p[i]});}}ll ans=1e18;if(cost<=c)ans=ur;debug(ans);rep(i,m){if(!used[i]){auto er=e();hld.path_query(u[i],v[i],[&](int l,int r){er=op(er,seg.prod(l,r));});if(cost-er.first+w[i]<=c)chmax(ans,p[i]);}}if(ans==1e18)ans=-1;cout<<ans<<endl;}