結果

問題 No.2642 Don't cut line!
ユーザー ゆにぽけゆにぽけ
提出日時 2024-02-19 22:29:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 141 ms / 4,000 ms
コード長 4,956 bytes
コンパイル時間 2,214 ms
コンパイル使用メモリ 160,068 KB
実行使用メモリ 34,180 KB
最終ジャッジ日時 2024-02-20 12:47:29
合計ジャッジ時間 5,740 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 132 ms
33,412 KB
testcase_02 AC 132 ms
32,900 KB
testcase_03 AC 130 ms
33,796 KB
testcase_04 AC 141 ms
34,052 KB
testcase_05 AC 132 ms
34,180 KB
testcase_06 AC 43 ms
6,676 KB
testcase_07 AC 43 ms
6,676 KB
testcase_08 AC 43 ms
6,676 KB
testcase_09 AC 43 ms
6,676 KB
testcase_10 AC 44 ms
6,676 KB
testcase_11 AC 43 ms
6,676 KB
testcase_12 AC 45 ms
6,676 KB
testcase_13 AC 42 ms
6,676 KB
testcase_14 AC 43 ms
6,676 KB
testcase_15 AC 46 ms
6,676 KB
testcase_16 AC 93 ms
24,068 KB
testcase_17 AC 104 ms
29,532 KB
testcase_18 AC 112 ms
30,988 KB
testcase_19 AC 80 ms
24,112 KB
testcase_20 AC 49 ms
12,160 KB
testcase_21 AC 45 ms
7,552 KB
testcase_22 AC 67 ms
18,764 KB
testcase_23 AC 127 ms
33,196 KB
testcase_24 AC 54 ms
16,348 KB
testcase_25 AC 54 ms
14,848 KB
testcase_26 AC 48 ms
8,448 KB
testcase_27 AC 77 ms
22,544 KB
testcase_28 AC 117 ms
30,740 KB
testcase_29 AC 50 ms
10,368 KB
testcase_30 AC 52 ms
13,440 KB
testcase_31 AC 96 ms
26,440 KB
testcase_32 AC 52 ms
12,288 KB
testcase_33 AC 2 ms
6,676 KB
testcase_34 AC 2 ms
6,676 KB
testcase_35 AC 1 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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();
}
0