結果
問題 | No.2642 Don't cut line! |
ユーザー | dyktr_06 |
提出日時 | 2024-02-19 22:14:47 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,211 bytes |
コンパイル時間 | 4,944 ms |
コンパイル使用メモリ | 273,748 KB |
実行使用メモリ | 12,988 KB |
最終ジャッジ日時 | 2024-09-29 02:09:55 |
合計ジャッジ時間 | 9,139 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
7,456 KB |
testcase_01 | AC | 127 ms
12,988 KB |
testcase_02 | AC | 125 ms
12,740 KB |
testcase_03 | AC | 119 ms
12,736 KB |
testcase_04 | AC | 120 ms
12,864 KB |
testcase_05 | AC | 121 ms
12,864 KB |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | AC | 85 ms
11,816 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 139 ms
12,736 KB |
testcase_17 | AC | 68 ms
11,964 KB |
testcase_18 | AC | 75 ms
12,388 KB |
testcase_19 | AC | 56 ms
11,172 KB |
testcase_20 | AC | 54 ms
10,932 KB |
testcase_21 | AC | 105 ms
11,464 KB |
testcase_22 | AC | 102 ms
11,388 KB |
testcase_23 | AC | 139 ms
12,796 KB |
testcase_24 | AC | 80 ms
10,016 KB |
testcase_25 | AC | 102 ms
10,432 KB |
testcase_26 | AC | 113 ms
11,408 KB |
testcase_27 | AC | 87 ms
10,852 KB |
testcase_28 | AC | 127 ms
12,436 KB |
testcase_29 | WA | - |
testcase_30 | AC | 108 ms
10,716 KB |
testcase_31 | AC | 105 ms
11,532 KB |
testcase_32 | AC | 112 ms
10,784 KB |
testcase_33 | AC | 4 ms
7,344 KB |
testcase_34 | AC | 4 ms
7,304 KB |
testcase_35 | AC | 4 ms
7,340 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define overload4(_1, _2, _3, _4, name, ...) name #define rep1(n) for(int i = 0; i < (int)(n); ++i) #define rep2(i, n) for(int i = 0; i < (int)(n); ++i) #define rep3(i, a, b) for(int i = (a); i < (int)(b); ++i) #define rep4(i, a, b, c) for(int i = (a); i < (int)(b); i += (c)) #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; --i) #define ALL(a) (a).begin(), (a).end() #define Sort(a) (sort((a).begin(), (a).end())) #define RSort(a) (sort((a).rbegin(), (a).rend())) #define UNIQUE(a) (a.erase(unique((a).begin(), (a).end()), (a).end())) typedef long long int ll; typedef unsigned long long ul; typedef long double ld; typedef vector<int> vi; typedef vector<long long> vll; typedef vector<char> vc; typedef vector<string> vst; typedef vector<double> vd; typedef vector<long double> vld; typedef pair<long long, long long> P; template<class T> long long sum(const T& a){ return accumulate(a.begin(), a.end(), 0LL); } template<class T> auto min(const T& a){ return *min_element(a.begin(), a.end()); } template<class T> auto max(const T& a){ return *max_element(a.begin(), a.end()); } const long long MINF = 0x7fffffffffff; const long long INF = 0x1fffffffffffffff; const long long MOD = 998244353; const long double EPS = 1e-9; const long double PI = acos(-1); template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p){ is >> p.first >> p.second; return is; } template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p){ os << "(" << p.first << ", " << p.second << ")"; return os; } template<typename T> istream &operator>>(istream &is, vector<T> &v){ for(T &in : v) is >> in; return is; } template<typename T> ostream &operator<<(ostream &os, const vector<T> &v){ for(int i = 0; i < (int) v.size(); ++i){ os << v[i] << (i + 1 != (int) v.size() ? " " : ""); } return os; } template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp){ for(auto &[key, val] : mp){ os << key << ":" << val << " "; } return os; } template <typename T> ostream &operator<<(ostream &os, const set<T> &st){ auto itr = st.begin(); for(int i = 0; i < (int)st.size(); ++i){ os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; } template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st){ auto itr = st.begin(); for(int i = 0; i < (int)st.size(); ++i){ os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; } template <typename T> ostream &operator<<(ostream &os, queue<T> q){ while(q.size()){ os << q.front() << " "; q.pop(); } return os; } template <typename T> ostream &operator<<(ostream &os, deque<T> q){ while(q.size()){ os << q.front() << " "; q.pop_front(); } return os; } template <typename T> ostream &operator<<(ostream &os, stack<T> st){ while(st.size()){ os << st.top() << " "; st.pop(); } return os; } template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq){ while(pq.size()){ os << pq.top() << " "; pq.pop(); } return os; } template<class T, class U> inline T vin(T& vec, U n) { vec.resize(n); for(int i = 0; i < (int) n; ++i) cin >> vec[i]; return vec; } template<class T> inline void vout(T vec, string s = "\n"){ for(auto x : vec) cout << x << s; } template<class... T> void in(T&... a){ (cin >> ... >> a); } void out(){ cout << '\n'; } template<class T, class... Ts> void out(const T& a, const Ts&... b){ cout << a; (cout << ... << (cout << ' ', b)); cout << '\n'; } template<class T, class U> void inGraph(vector<vector<T>>& G, U n, U m, bool directed = false){ G.resize(n); for(int i = 0; i < m; ++i){ int a, b; cin >> a >> b; a--, b--; G[a].push_back(b); if(!directed) G[b].push_back(a); } } template <typename X> struct SegTree{ using FX = function<X(X, X)>; // X•X -> X となる関数の型 int n; FX fx; const X ex; vector<X> dat; SegTree(int n_, const FX &fx_, const X &ex_) : n(), fx(fx_), ex(ex_){ int x = 1; while(n_ > x){ x *= 2; } n = x; dat.assign(n * 2, ex); } X get(int i) const { return dat[i + n]; } void set(int i, const X &x){ dat[i + n] = x; } void build(){ for(int k = n - 1; k >= 1; k--) dat[k] = fx(dat[k * 2], dat[k * 2 + 1]); } void update(int i, const X &x){ i += n; dat[i] = x; while(i > 0){ i >>= 1; // parent dat[i] = fx(dat[i * 2], dat[i * 2 + 1]); } } X query(int a, int b){ X vl = ex; X vr = ex; int l = a + n; int r = b + n; while(l < r){ if(l & 1) vl = fx(vl, dat[l++]); if(r & 1) vr = fx(dat[--r], vr); l >>= 1; r >>= 1; } return fx(vl, vr); } X operator [](int i) const { return dat[i + n]; } }; struct UnionFind{ vector<int> par; vector<int> edg; UnionFind(int N) : par(N), edg(N){ for(int i = 0; i < N; ++i){ par[i] = -1; edg[i] = 0; } } int root(int x){ if(par[x] < 0) return x; return par[x] = root(par[x]); } void unite(int x, int y){ int rx = root(x); int ry = root(y); if(rx == ry){ edg[rx]++; return; } par[ry] = par[rx] + par[ry]; par[rx] = ry; edg[ry] += edg[rx] + 1; } bool same(int x, int y){ int rx = root(x); int ry = root(y); return rx == ry; } long long size(int x){ return -par[root(x)]; } long long edge(int x){ return edg[root(x)]; } }; template <typename T> struct compress{ vector<T> sorted, compressed; compress(const vector<T>& vec){ int n = vec.size(); compressed.resize(n); for(T x : vec){ sorted.emplace_back(x); } sort(sorted.begin(), sorted.end()); sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end()); for(int i = 0; i < n; ++i){ compressed[i] = lower_bound(sorted.begin(), sorted.end(), vec[i]) - sorted.begin(); } } int get(const T& x) const{ return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin(); } T inv(const T& x) const{ return sorted[x]; } size_t size() const{ return sorted.size(); } vector<T> getCompressed() const{ return compressed; } }; ll n, k, c; vll u, v, w, p; void input(){ in(n, k, c); u.resize(k); v.resize(k); w.resize(k); p.resize(k); rep(i, k){ in(u[i], v[i], w[i], p[i]); } } void solve(){ rep(i, k) u[i]--, v[i]--; vector<P> e(k); rep(i, k){ e[i] = {w[i], i}; } Sort(e); auto fx = [](P a, P b){ if(a.first <= b.first){ return a; }else{ return b; } }; P ex = {INF, -1}; SegTree<P> seg(100001, fx, ex); rep(i, k){ seg.update(p[i], fx(seg[i], {w[i], i})); } ll ok = 0, ng = 100001; while(abs(ok - ng) > 1){ ll mid = (ok + ng) / 2; UnionFind uf(n); ll cost = 0; auto [mn, idx] = seg.query(mid, 100001); if(idx == -1){ ng = mid; continue; } uf.unite(u[idx], v[idx]); cost += w[idx]; rep(i, k){ auto [weight, idx] = e[i]; if(uf.same(u[idx], v[idx])) continue; uf.unite(u[idx], v[idx]); cost += w[idx]; } if(cost <= c){ ok = mid; }else{ ng = mid; } } if(ok == 0) out(-1); else out(ok); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(20); input(); solve(); }