Submission #140538

#	Time	Username	Problem	Language	Result	Execution time	Memory
140538		luciocf	Bridges (APIO19_bridges)	C++14	27 / 100	414 ms	8888 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];

struct Op
{
	int u, w, ind;
} query[maxm];

int n, m, q;
int tot;

int ans[maxm];

int pai[maxn], peso[maxn];

vector<pii> grafo[maxn];

bool comp(Edge a, Edge b) {return a.w > b.w;}
bool comp2(Op a, Op 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)
{
	tot++;

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

void solve_small(void)
{
	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();

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

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

int main(void)
{
	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);
	
	if (n <= 1000 && m <= 1000 && q <= 10000)
	{
		solve_small();
		return 0;
	}

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

		scanf("%d %d", &query[i].u, &query[i].w);
		query[i].ind = i;
	}

	sort(edge+1, edge+m+1, comp);
	sort(query+1, query+q+1, comp2);

	init();

	int p = 1;

	for (int i = 1; i <= q; i++)
	{
		while (edge[p].w >= query[i].w)
		{
			Join(edge[p].u, edge[p].v);
			p++;
		}

		ans[query[i].ind] = peso[Find(query[i].u)];
	}

	for (int i = 1; i <= q; i++)
		printf("%d\n", ans[i]);
}

Compilation message (stderr)

bridges.cpp: In function 'void solve_small()':
bridges.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &op);
   ~~~~~^~~~~~~~~~~
bridges.cpp:97: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:104:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &u, &w);
    ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:118: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:123: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:128:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &fuckyou);
   ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &query[i].u, &query[i].w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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