結果
問題 | No.2642 Don't cut line! |
ユーザー | ぷら |
提出日時 | 2024-02-19 22:17:35 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 159 ms / 4,000 ms |
コード長 | 5,353 bytes |
コンパイル時間 | 2,528 ms |
コンパイル使用メモリ | 168,132 KB |
実行使用メモリ | 26,632 KB |
最終ジャッジ日時 | 2024-09-29 03:33:55 |
合計ジャッジ時間 | 7,337 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 159 ms
25,696 KB |
testcase_02 | AC | 153 ms
25,096 KB |
testcase_03 | AC | 153 ms
25,988 KB |
testcase_04 | AC | 155 ms
26,500 KB |
testcase_05 | AC | 153 ms
26,632 KB |
testcase_06 | AC | 90 ms
6,816 KB |
testcase_07 | AC | 90 ms
6,820 KB |
testcase_08 | AC | 87 ms
6,816 KB |
testcase_09 | AC | 87 ms
6,820 KB |
testcase_10 | AC | 89 ms
6,816 KB |
testcase_11 | AC | 89 ms
6,816 KB |
testcase_12 | AC | 91 ms
6,820 KB |
testcase_13 | AC | 88 ms
6,816 KB |
testcase_14 | AC | 89 ms
6,816 KB |
testcase_15 | AC | 92 ms
6,820 KB |
testcase_16 | AC | 73 ms
12,164 KB |
testcase_17 | AC | 132 ms
22,964 KB |
testcase_18 | AC | 136 ms
23,600 KB |
testcase_19 | AC | 99 ms
19,240 KB |
testcase_20 | AC | 83 ms
10,444 KB |
testcase_21 | AC | 47 ms
6,816 KB |
testcase_22 | AC | 53 ms
9,848 KB |
testcase_23 | AC | 145 ms
25,464 KB |
testcase_24 | AC | 79 ms
12,460 KB |
testcase_25 | AC | 95 ms
11,656 KB |
testcase_26 | AC | 132 ms
7,848 KB |
testcase_27 | AC | 92 ms
17,628 KB |
testcase_28 | AC | 133 ms
23,796 KB |
testcase_29 | AC | 123 ms
8,876 KB |
testcase_30 | AC | 107 ms
10,860 KB |
testcase_31 | AC | 110 ms
20,648 KB |
testcase_32 | AC | 114 ms
10,024 KB |
testcase_33 | AC | 2 ms
6,816 KB |
testcase_34 | AC | 2 ms
6,820 KB |
testcase_35 | AC | 2 ms
6,816 KB |
ソースコード
#include <string.h> #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <iterator> #include <list> #include <map> #include <memory> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; struct UnionFind { vector<int> par; vector<int> size; UnionFind() {} UnionFind(int n) { par.resize(n); size.resize(n,1); for(int i = 0; i < n; i++) { par[i] = i; } } int find(int x) { if(par[x] == x) { return x; } return par[x] = find(par[x]); } bool same(int x, int y) { return find(x) == find(y); } int consize(int x) { return size[find(x)]; } bool unite(int x, int y) { x = find(x); y = find(y); if(x == y) { return false; } if(size[x] > size[y]) { swap(x,y); } par[x] = y; size[y] += size[x]; return true; } }; int inf = 1001001001; template <typename T> struct SegmentTree { int n; vector<T> dat; SegmentTree() {} SegmentTree(int N) { n = 1; while(n < N) { n *= 2; } dat.resize(2*n-1,-inf); } void update(int x, T val) { x += n-1; dat[x] = val; while(x > 0) { x = (x-1)/2; dat[x] = max(dat[2*x+1],dat[2*x+2]); } } T query(int a, int b, int k, int l, int r) { if(r <= a || b <= l) return -inf; if(a <= l && r <= b) return dat[k]; T vl = query(a, b, 2*k+1, l, (l+r)/2); T vr = query(a, b, 2*k+2, (l+r)/2, r); return max(vl, vr); } T query(int a,int b) {//[a,b) return query(a,b,0,0,n); } }; struct HLD { // 根が 0 でない時に注意 vector<int>p,sz,in,nxt; SegmentTree<int> seg; void dfs1(vector<vector<int>>&c,int v = 0) { sz[v] = 1; for(int &w:c[v]) { dfs1(c,w); sz[v] += sz[w]; if(sz[w] > sz[c[v][0]]) { swap(w,c[v][0]); } } } void dfs2(vector<vector<int>>&c,int &t,int v = 0) { in[v] = t; t++; for(int w:c[v]) { if(w == c[v][0]) { nxt[w] = nxt[v]; } else { nxt[w] = w; } dfs2(c,t,w); } } HLD(vector<int>&A,vector<int>&p,vector<vector<int>>&c):p(p) { int N = A.size(); sz.resize(N,0); dfs1(c); in.resize(N,0); nxt.resize(N,0); int t = 0; dfs2(c,t); vector<long long>tmp(N); for(int i = 0; i < N; i++) { tmp[in[i]] = A[i]; } SegmentTree<int>init(tmp.size()); for(int i = 1; i < tmp.size(); i++) { init.update(i,tmp[i]); } seg = init; } int lca(int u,int v) { while(true) { if(in[u] > in[v]) { swap(u,v); } if(nxt[u] == nxt[v]) { return u; } v = p[nxt[v]]; } } int query(int u,int v) { int w = lca(u,v); int ans = 0; while(nxt[u] != nxt[w]) { ans = max(ans,seg.query(in[nxt[u]],in[u]+1)); u = p[nxt[u]]; } ans = max(ans,seg.query(in[w]+1,in[u]+1)); while(nxt[v] != nxt[w]) { ans = max(ans,seg.query(in[nxt[v]],in[v]+1)); v = p[nxt[v]]; } ans = max(ans,seg.query(in[w]+1,in[v]+1)); return ans; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N,K; long long C; cin >> N >> K >> C; vector<int>u(K),v(K),w(K),p(K); vector<array<int,3>>tmp; for(int i = 0; i < K; i++) { cin >> u[i] >> v[i] >> w[i] >> p[i]; u[i]--; v[i]--; tmp.push_back({w[i],u[i],v[i]}); } sort(tmp.begin(),tmp.end()); vector<vector<pair<int,int>>>ki(N); UnionFind uf(N); long long cost = 0; for(int i = 0; i < K; i++) { if(uf.unite(tmp[i][1],tmp[i][2])) { cost += tmp[i][0]; ki[tmp[i][1]].push_back({tmp[i][2],tmp[i][0]}); ki[tmp[i][2]].push_back({tmp[i][1],tmp[i][0]}); } } if(cost > C) { cout << -1 << "\n"; return 0; } vector<int>P(N,-1); vector<int>a(N,-1); vector<vector<int>>c(N); queue<int>que; que.push(0); while(!que.empty()) { int x = que.front(); que.pop(); for(auto i:ki[x]) { if(i.first != 0 && P[i.first] == -1) { P[i.first] = x; c[x].push_back(i.first); a[i.first] = i.second; que.push(i.first); } } } HLD hld(a,P,c); int ans = 0; for(int i = 0; i < K; i++) { int mx = hld.query(u[i],v[i]); if(cost-mx+w[i] <= C) { ans = max(ans,p[i]); } } cout << ans << "\n"; }