結果
問題 | No.2642 Don't cut line! |
ユーザー |
![]() |
提出日時 | 2024-02-19 22:17:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 181 ms / 4,000 ms |
コード長 | 5,353 bytes |
コンパイル時間 | 2,442 ms |
コンパイル使用メモリ | 161,816 KB |
最終ジャッジ日時 | 2025-02-19 17:07:37 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#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";}