#952845 (C++17) No.2642 Don't cut line!

提出ソース

結果

問題	No.2642 Don't cut line!
ユーザー	ゆにぽけ
提出日時	2024-02-19 22:25:07
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	4,956 bytes
コンパイル時間	2,174 ms
コンパイル使用メモリ	160,388 KB
実行使用メモリ	34,044 KB
最終ジャッジ日時	2024-09-29 02:18:39
合計ジャッジ時間	9,006 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	RE	-
testcase_01	AC	156 ms 33,292 KB
testcase_02	AC	166 ms 32,776 KB
testcase_03	AC	166 ms 33,672 KB
testcase_04	AC	144 ms 33,928 KB
testcase_05	AC	145 ms 34,044 KB
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	AC	111 ms 23,944 KB
testcase_17	AC	135 ms 29,376 KB
testcase_18	AC	139 ms 30,860 KB
testcase_19	AC	91 ms 23,988 KB
testcase_20	AC	50 ms 12,032 KB
testcase_21	AC	45 ms 7,424 KB
testcase_22	AC	77 ms 18,652 KB
testcase_23	AC	154 ms 33,032 KB
testcase_24	AC	58 ms 16,092 KB
testcase_25	RE	-
testcase_26	RE	-
testcase_27	AC	85 ms 22,420 KB
testcase_28	AC	140 ms 30,616 KB
testcase_29	RE	-
testcase_30	RE	-
testcase_31	AC	120 ms 26,316 KB
testcase_32	AC	58 ms 12,160 KB
testcase_33	AC	2 ms 6,820 KB
testcase_34	AC	2 ms 6,820 KB
testcase_35	AC	2 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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[cur][k]);
					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[cur][k]);
					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();
}

yukicoder

結果

テストケース

ソースコード