Submission #140536

#	Time	Username	Problem	Language	Result	Execution time	Memory
140536		luciocf	Bridges (APIO19_bridges)	C++14	13 / 100	3029 ms	8440 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 5e4+10;
const int maxm = 1e5+10;

struct Edge
{
	int u, v, w;
} edge[maxm], aux[maxm];

int n, m;
int ans;

int pai[maxn], peso[maxn];

vector<pii> grafo[maxn];

bool comp(Edge a, Edge b) {return a.w > b.w;}

void init(void)
{
	for (int i = 1; i <= n; i++)
	{
		pai[i] = i, peso[i] = 1;
		grafo[i].clear();
	}
}

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

void Join(int x, int y)
{
	x = Find(x), y = Find(y);
	if (x == y) return;

	if (peso[x] < peso[y]) swap(x, y);

	pai[y] = x, peso[x] += peso[y];
}

void get_mst(void)
{
	init();

	for (int i = 1; i <= m; i++)
		aux[i] = edge[i];

	sort(aux+1, aux+m+1, comp);

	for (int i = 1; i <= m; i++)
	{
		if (Find(aux[i].u) != Find(aux[i].v))
		{
			Join(aux[i].u, aux[i].v);

			grafo[aux[i].u].push_back({aux[i].v, aux[i].w});
			grafo[aux[i].v].push_back({aux[i].u, aux[i].w});
		}
	}
}

void dfs(int u, int p, int w)
{
	ans++;

	for (auto v: grafo[u])
		if (v.first != p && v.second >= w)
			dfs(v.first, u, w);
}

int main(void)
{
	int q;
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);

		edge[i] = {u, v, w};
	}

	scanf("%d", &q);

	for (int i = 1; i <= q; i++)
	{
		int op;
		scanf("%d", &op);

		if (op == 1)
		{
			int ind, w;
			scanf("%d %d", &ind, &w);

			edge[ind].w = w;
		}
		else
		{
			int u, w;
			scanf("%d %d", &u, &w);

			get_mst();

			ans = 0;
			dfs(u, 0, w);

			printf("%d\n", ans);
		}
	}
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &op);
   ~~~~~^~~~~~~~~~~
bridges.cpp:102:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &ind, &w);
    ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:109:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &u, &w);
    ~~~~~^~~~~~~~~~~~~~~~~

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