Submission #569135

#	Time	Username	Problem	Language	Result	Execution time	Memory
569135		aryan12	Bridges (APIO19_bridges)	C++17	14 / 100	136 ms	15252 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 5e4 + 5;
// vector<array<int, 2> > g[N];
vector<array<int, 3> > edges(N * 2);
int par[N], siz[N];

// int dfs(int node, int wt)
// {
// 	vis[node] = true;
// 	int ans = 1;
// 	for(auto [to, idx]: g[node])
// 	{
// 		int cur_wt = edges[idx][2];
// 		if(cur_wt >= wt && !vis[to])
// 		{
// 			ans += dfs(to, wt);
// 		}
// 	}
// 	return ans;
// }

int Find(int x)
{
	if(x == par[x]) return x;
	return par[x] = Find(par[x]);
}

void Unite(int a, int b)
{
	a = Find(a), b = Find(b);
	if(a == b) return;
	siz[a] += siz[b];
	par[b] = a;
}

bool cmp(array<int, 4> a, array<int, 4> b)
{
	if(a[3] == b[3]) return a[0] < b[0];
	return a[3] > b[3];
}

void Solve() 
{
	int n, m;
	cin >> n >> m;
	for(int i = 0; i <= n; i++)
	{
		par[i] = i;
		siz[i] = 1;
	}
	vector<array<int, 4> > temp;
	for(int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		// g[u].push_back({v, i});
		// g[v].push_back({u, i});
		edges[i] = {u, v, w};
		temp.push_back({0, u, v, w});
	}
	int q;
	cin >> q;
	vector<int> ans(q + 1);
	for(int i = 1; i <= q; i++)
	{
		int command, node, start_wt;
		cin >> command >> node >> start_wt;
		temp.push_back({command, i, node, start_wt});
	}
	sort(temp.begin(), temp.end(), cmp);
	for(int i = 0; i < temp.size(); i++)
	{
		if(temp[i][0] == 0)
		{
			Unite(temp[i][1], temp[i][2]);
		}
		else
		{
			ans[temp[i][1]] = siz[Find(temp[i][2])];
		}
	}
	for(int i = 1; i <= q; i++)
	{
		cout << ans[i] << "\n";
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void Solve()':
bridges.cpp:76:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i = 0; i < temp.size(); i++)
      |                 ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27