結果
問題 | No.2642 Don't cut line! |
ユーザー | ゆにぽけ |
提出日時 | 2024-02-19 22:29:23 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 162 ms / 4,000 ms |
コード長 | 4,956 bytes |
コンパイル時間 | 1,978 ms |
コンパイル使用メモリ | 159,804 KB |
実行使用メモリ | 34,056 KB |
最終ジャッジ日時 | 2024-09-29 03:35:32 |
合計ジャッジ時間 | 6,033 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 145 ms
33,124 KB |
testcase_02 | AC | 162 ms
32,776 KB |
testcase_03 | AC | 142 ms
33,668 KB |
testcase_04 | AC | 159 ms
33,800 KB |
testcase_05 | AC | 153 ms
34,056 KB |
testcase_06 | AC | 43 ms
6,816 KB |
testcase_07 | AC | 44 ms
6,816 KB |
testcase_08 | AC | 43 ms
6,820 KB |
testcase_09 | AC | 43 ms
6,820 KB |
testcase_10 | AC | 43 ms
6,816 KB |
testcase_11 | AC | 44 ms
6,820 KB |
testcase_12 | AC | 45 ms
6,816 KB |
testcase_13 | AC | 44 ms
6,820 KB |
testcase_14 | AC | 44 ms
6,820 KB |
testcase_15 | AC | 43 ms
6,816 KB |
testcase_16 | AC | 103 ms
23,944 KB |
testcase_17 | AC | 120 ms
29,376 KB |
testcase_18 | AC | 142 ms
30,860 KB |
testcase_19 | AC | 88 ms
23,988 KB |
testcase_20 | AC | 48 ms
11,904 KB |
testcase_21 | AC | 45 ms
7,424 KB |
testcase_22 | AC | 73 ms
18,636 KB |
testcase_23 | AC | 144 ms
32,944 KB |
testcase_24 | AC | 58 ms
16,096 KB |
testcase_25 | AC | 54 ms
14,720 KB |
testcase_26 | AC | 48 ms
8,448 KB |
testcase_27 | AC | 82 ms
22,296 KB |
testcase_28 | AC | 138 ms
30,592 KB |
testcase_29 | AC | 48 ms
10,240 KB |
testcase_30 | AC | 54 ms
13,184 KB |
testcase_31 | AC | 101 ms
26,312 KB |
testcase_32 | AC | 52 ms
12,160 KB |
testcase_33 | AC | 2 ms
6,816 KB |
testcase_34 | AC | 2 ms
6,820 KB |
testcase_35 | AC | 2 ms
6,820 KB |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <array>#include <iterator>#include <string>#include <cctype>#include <cstring>#include <cstdlib>#include <cassert>#include <cmath>#include <ctime>#include <iomanip>#include <numeric>#include <stack>#include <queue>#include <map>#include <unordered_map>#include <set>#include <unordered_set>#include <bitset>#include <random>#include <utility>#include <functional>using namespace std;struct LCA{private:int N,K;vector<vector<int>> G;vector<vector<int>> par;vector<int> depth;int edge_count;void dfs(int u,int p){par[0][u] = p;if(p != -1){depth[u] = depth[p] + 1;}for(int v : G[u]) if(v != p){dfs(v,u);}}public:LCA() {}LCA(int N_){N = N_;int M = 1;K = 0;while(M < N){M <<= 1;K++;}if(N == 1){K++;}par.assign(K,vector<int>(N,-1));G.resize(N);depth.assign(N,0);edge_count = 0;}void add_edge(int u,int v,bool oriented = false){assert(0 <= u && u < N && 0 <= v && v < N);G[u].push_back(v);if(!oriented){G[v].push_back(u);}edge_count++;}void build(int root = 0){assert(0 <= root && root < N);assert(edge_count == N - 1);dfs(root,-1);for(int k = 1;k < K;k++){for(int u = 0;u < N;u++) if(par[k - 1][u] != -1){par[k][u] = par[k - 1][par[k - 1][u]];}}}int lca(int u,int v){assert(0 <= u && u < N && 0 <= v && v < N);if(depth[u] < depth[v]){swap(u,v);}for(int k = 0;k < K;k++){if((depth[v] - depth[u]) >> k & 1){u = par[k][u];}}if(u == v){return u;}for(int k = K;k--;){if(par[k][u] == par[k][v]);else{u = par[k][u];v = par[k][v];}}assert(par[0][u] == par[0][v]);return par[0][u];}int get_depth(int u){assert(0 <= u && u < N);return depth[u];}int get_log(){return K;}int get_par(int u,int k){assert(0 <= u && u < N);assert(0 <= k && k < K);return par[k][u];}};#include<algorithm>#include<vector>#include<cassert>using namespace std;struct UnionFind{private:int n;vector<int> par,siz;public:UnionFind(int n) :n(n),par(n,-1),siz(n,1) {}int root(int u){assert(0 <= u && u < n);return (par[u] < 0 ? u:par[u] = root(par[u]));}bool same(int u,int v){assert(0 <= u && u < n && 0 <= v && v < n);return root(u) == root(v);}bool unite(int u,int v){assert(0 <= u && u < n && 0 <= v && v < n);u = root(u),v = root(v);if(u == v) return false;if(siz[u] < siz[v]) swap(u,v);siz[u] += siz[v];par[v] = u;return true;}int size(int u){assert(0 <= u && u < n);return siz[root(u)];}vector<vector<int>> components(){vector<vector<int>> ret(n);for(int u = 0;u < n;u++) ret[root(u)].push_back(u);ret.erase(remove_if(ret.begin(),ret.end(),[](vector<int> v) { return v.empty();}),ret.end());return ret;}};void Main(){int N,M;long long C;cin >> N >> M >> C;vector<tuple<int,int,int,int>> E(M);for(int i = 0;i < M;i++){int u,v,w,p;cin >> u >> v >> w >> p;u--; v--;E[i] = make_tuple(w,u,v,p);}sort(E.begin(),E.end());LCA lca(N);vector<vector<pair<int,int>>> G(N);UnionFind uf(N);vector<int> used(M);int ans = 0;long long cost = 0;for(int i = 0;i < M;i++){const auto [w,u,v,p] = E[i];if(uf.unite(u,v)){cost += w;ans = max(ans,p);lca.add_edge(u,v);G[u].push_back(make_pair(v,w));G[v].push_back(make_pair(u,w));used[i] = 1;}}if(cost > C){cout << "-1\n";return;}lca.build();int K = lca.get_log();vector<vector<int>> dp(K,vector<int>(N,-(int)1e9));auto dfs = [&](auto dfs,int u,int p,int pw) -> void{if(p != -1){dp[0][u] = pw;}for(const auto &[v,w] : G[u]){if(v == p){continue;}dfs(dfs,v,u,w);}};dfs(dfs,0,-1,0);for(int k = 1;k < K;k++){for(int u = 0;u < N;u++){int p = lca.get_par(u,k - 1);if(p == -1){continue;}dp[k][u] = max(dp[k - 1][u],dp[k - 1][p]);}}for(int i = 0;i < M;i++){if(used[i]){continue;}const auto &[w,u,v,p] = E[i];if(p <= ans){continue;}int x = lca.lca(u,v);int mx = 0;{int d = lca.get_depth(u) - lca.get_depth(x);int cur = u;for(int k = 0;k < K;k++){if(d >> k & 1){mx = max(mx,dp[k][cur]);cur = lca.get_par(cur,k);}}assert(cur == x);}{int d = lca.get_depth(v) - lca.get_depth(x);int cur = v;for(int k = 0;k < K;k++){if(d >> k & 1){mx = max(mx,dp[k][cur]);cur = lca.get_par(cur,k);}}assert(cur == x);}if(cost - mx + w <= C){ans = max(ans,p);}}cout << ans << "\n";}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1;/* cin >> tt; */while(tt--) Main();}