Submission #227316

#	Time	Username	Problem	Language	Result	Execution time	Memory
227316		luciocf	Bridges (APIO19_bridges)	C++14	0 / 100	3094 ms	34656 KiB

bridges

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 3e5+10;
const int sq = 320;

struct Edge
{
	int u, v, w, ind;
} edge[maxn];

struct Query
{
	int op, a, b;
} query[maxn];

int pai[maxn], peso[maxn];

int ans[maxn];

bool mark[maxn];
bool mark_edge[maxn], mark_inside[maxn];

set<int> edge_sorted[maxn];
vector<pii> grafo[maxn];

void compress(int m, int q)
{
	map<int, int> mp;

	for (int i = 1; i <= m; i++)
		mp[edge[i].w] = 0;
	for (int i = 0; i < q; i++)
		mp[query[i].b] = 0;

	int aux = 0;
	for (auto &x: mp)
		x.second = ++aux;

	for (int i = 1; i <= m; i++)
		edge[i].w = mp[edge[i].w];
	for (int i = 0; i < q; i++)
		query[i].b = mp[query[i].b];
}

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

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 dfs(int u, int lim, int ind)
{
	mark[u] = 1;
	ans[ind] += peso[u];

	for (auto e: grafo[u])
	{
		int v = e.ff, w = e.ss;

		if (w >= lim && !mark[v])
			dfs(v, lim, ind);
	}
}

int main(void)
{
	int n, m;
	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, i};
	}

	int q;
	scanf("%d", &q);

	for (int i = 0; i < q; i++)
		scanf("%d %d %d", &query[i].op, &query[i].a, &query[i].b);

	compress(m, q);

	for (int i = 1; i <= m; i++)
		edge_sorted[edge[i].w].insert(i);

	for (int i = 0; i < q; i += sq)
	{
		init(n);
		int last = min(q, i+sq);

		for (int j = i; j < last; j++)
			if (query[j].op == 1)
				mark_edge[query[j].a] = 1;

		vector<pii> bucket;

		for (int j = i; j < last; j++)
			if (query[j].op == 2)
				bucket.push_back({query[j].b, j});

		sort(bucket.begin(), bucket.end(), greater<pii>());

		int cur_w = maxn-1;

		for (auto qry: bucket)
		{
			int w = qry.ff, ind = qry.ss;

			while (cur_w >= w)
			{
				for (auto e: edge_sorted[cur_w])
				{
					if (mark_edge[e]) continue;

					Join(edge[e].u, edge[e].v);
				}

				cur_w--;
			}

			for (int j = ind-1; j >= i; j--)
			{
				if (query[j].op == 2) continue;

				int aux = query[j].a;

				if (!mark_inside[aux])
				{
					grafo[Find(edge[aux].u)].push_back({Find(edge[aux].v), query[j].b});
					grafo[Find(edge[aux].v)].push_back({Find(edge[aux].u), query[j].b});
					mark_inside[aux] = 1;
				}
			}

			for (int j = ind+1; j < last; j++)
			{
				if (query[j].op == 2) continue;

				int aux = query[j].a;

				if (!mark_inside[aux])
				{
					grafo[Find(edge[aux].u)].push_back({Find(edge[aux].v), edge[aux].w});
					grafo[Find(edge[aux].v)].push_back({Find(edge[aux].u), edge[aux].w});
				}
			}

			dfs(Find(query[ind].a), query[ind].b, ind);

			for (int j = ind-1; j >= i; j--)
			{
				if (query[j].op == 2) continue;

				int aux = query[j].a;

				mark_inside[aux] = 0;
				mark[Find(edge[aux].u)] = mark[Find(edge[aux].v)] = 0;
				grafo[Find(edge[aux].u)].clear(); grafo[Find(edge[aux].v)].clear();
			}

			for (int j = ind+1; j < last; j++)
			{
				if (query[j].op == 2) continue;

				int aux = query[j].a;

				mark[Find(edge[aux].u)] = mark[Find(edge[aux].v)] = 0;
				grafo[Find(edge[aux].u)].clear();
				grafo[Find(edge[aux].v)].clear();
			}

		}

		for (int j = i; j < last; j++)
		{
			if (query[j].op == 1)
			{
				edge_sorted[edge[query[j].a].w].erase(query[j].a);
				edge[query[j].a].w = query[j].b;
				edge_sorted[query[j].b].insert(query[j].a);

				mark_edge[query[j].a] = 0;
			}
		}
	}

	for (int i = 0; i < q; i++)
		if (query[i].op == 2)
			printf("%d\n", ans[i]);
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:91: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:96: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:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &query[i].op, &query[i].a, &query[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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