Submission #527037

#	Time	Username	Problem	Language	Result	Execution time	Memory
527037		LucaDantas	Bridges (APIO19_bridges)	C++17	13 / 100	3097 ms	9148 KiB

bridges

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

constexpr int maxn = 1e5+10, maxq = maxn, B = maxn; // primeira subtask fds DEBUG <-------------------------------------->

struct DSU {
	int pai[maxn], peso[maxn];
	DSU() { for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1; }
	void init() { for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1; }
	int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
	void join(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) return;
		if(peso[a] < peso[b]) swap(a, b);
		pai[b] = a;
		peso[a] += peso[b];
	}
	void reset(int a) { pai[a] = a, peso[a] = 1; }
	int sz(int a) { return peso[find(a)]; }
} dsu, dsu2;

struct Edge { int a, b, d, id; } e[maxn], certo[maxn];

struct Query { int tipo, x, y, t; } qr[maxq];

bool special[maxn], foi[maxn];

int ans[maxq];

int main() {
	memset(ans, -1, sizeof ans);
	
	int n, m; scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++)
		scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].d), e[i].id = i, certo[i] = e[i];

	int q; scanf("%d", &q);
	for(int i = 0; i < q; i++) {
		scanf("%d %d %d", &qr[i].tipo, &qr[i].x, &qr[i].y);
		if(qr[i].tipo == 1) --qr[i].x;
		qr[i].t = i;
	}

	// ordenar as arestas pelo peso decrescente
	sort(e, e+m, [](const Edge& a, const Edge& b) { return a.d > b.d; });

	for(int k = 0; k < q; k += B) {
		vector<Query> ask;

		for(int i = k; i < min(q, k+B); i++) {
			if(qr[i].tipo == 1) // update
				special[qr[i].x] = 1 /*, printf("marquei %d\n", qr[i].x)*/ ;
			else ask.push_back(qr[i]);
		}

		sort(ask.begin(), ask.end(), [](const Query& a, const Query& b) { return a.y > b.y; }); // y==peso, ordeno pelo peso decrescente

		for(int i = 0, ptr = 0; i < (int)ask.size(); i++) {

			// printf("QUERY %d\n", ask[i].t);

			for(; ptr < m && e[ptr].d >= ask[i].y; ptr++) {
				if(!special[e[ptr].id])
					dsu.join(e[ptr].a, e[ptr].b) /*, printf("juntei %d\n", e[ptr].id)*/ ;
				// else printf("não juntei %d\n", e[ptr].id);
			}
			// printf("proximo %d\n", e[ptr].d);

			vector<int> ver = {dsu.find(ask[i].x)}; // todos os caras que eu vou olhar no dsu2 pra ver se está junto ao vertice da pergunta

			// ERRADO
			for(int j = ask[i].t-1; j >= k; j--) { // vejo todos os updates anteriores pra ver se adiciono ou não
				// puts("Hm");
				if(qr[j].tipo == 1 && qr[j].y >= ask[i].y && !foi[qr[j].x]) {
					int id = qr[j].x;
					dsu2.join(dsu.find(certo[id].a), dsu.find(certo[id].b));
					ver.push_back(dsu.find(certo[id].a)), ver.push_back(dsu.find(certo[id].b));
				}
				if(qr[j].tipo == 1)
					foi[qr[j].x] = 1;
			}

			// ERRADO
			for(int j = ask[i].t; j < min(q, k+B); j++) {
				// printf("hm %d\n", qr[j].x);
				if(qr[j].tipo == 1 && certo[qr[j].x].d >= ask[i].y && !foi[qr[j].x]) {
					int id = qr[j].x;
					dsu2.join(dsu.find(certo[id].a), dsu.find(certo[id].b));
					ver.push_back(dsu.find(certo[id].a)), ver.push_back(dsu.find(certo[id].b));
				}
			}

			for(int j = ask[i].t-1; j >= k; j--) { // vejo todos os updates anteriores pra ver se adiciono ou não
				foi[qr[j].x] = 0;
			}

			/* puts("VER");
			for(int x : ver)
				printf("%d ", x);
			puts(""); */

			int val = 0;

			for(int x : ver) {
				if(!foi[x] && dsu2.find(dsu.find(ask[i].x)) == dsu2.find(x))
					foi[x] = 1, val += dsu.sz(x);
			}

			for(int x : ver) dsu2.reset(x), foi[x] = 0;
			// dsu2.init(); memset(foi, 0, sizeof foi); // DEBUG <-------------------------------------->

			ans[ask[i].t] = val;

			// puts("");

		}


		// reiniciar as coisas pro próximo bloco
	}

	// puts("\nFIM\n");

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

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:33:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  int n, m; scanf("%d %d", &n, &m);
      |            ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   scanf("%d %d %d", &e[i].a, &e[i].b, &e[i].d), e[i].id = i, certo[i] = e[i];
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
bridges.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |   scanf("%d %d %d", &qr[i].tipo, &qr[i].x, &qr[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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