Submission #196943

#	Time	Username	Problem	Language	Result	Execution time	Memory
196943		tincamatei	Bridges (APIO19_bridges)	C++14	13 / 100	3099 ms	21200 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 50000;
const int MAX_M = 100000;
const int MAX_Q = 100000;
const int BUCK = 315;

int sef[1+MAX_N], size[1+MAX_N];
vector<int> graph[1+MAX_N];

void initDSU(int N) {
	for(int i = 1; i <= N; ++i) {
		sef[i] = i;
		size[i] = 1;
	}
}

int myfind(int a) {
	if(a == sef[a])
		return a;
	sef[a] = myfind(sef[a]);
	return sef[a];
}

void myunion(int a, int b) {
	int sa = myfind(a), sb = myfind(b);
	if(sa != sb) {
		sef[sa] = sb;
		size[sb] += size[sa];
	}
}

struct Edge {
	int a, b, w, id;
	
	bool operator< (const Edge &x) const {
		return make_pair(-w, id) < make_pair(-x.w, x.id);
	}
} edges[1+MAX_M];


struct Query {
	bool update;
	int a, b;
	int rez;
} queries[1+MAX_Q];

bool viz[1+MAX_N];
vector<int> dfsStack;

int bfs(int nod) {
	deque<int> coada;
	coada.push_back(nod);
	int sum = 0;

	while(!coada.empty()) {
		nod = coada.front();
		coada.pop_front();
		viz[nod] = true;
		dfsStack.push_back(nod);

		sum += size[nod];
		
		for(auto it: graph[nod])
			if(!viz[it]) {
				coada.push_back(it);
				viz[it] = true;
			}
	}

	return sum;
}

void undoDfs() {
	for(auto it: dfsStack)
		viz[it] = false;
	dfsStack.clear();
}

set<Edge> allEdges;
bool blockedEdges[1+MAX_M];
bool bucketBlocked[1+MAX_M];

bool cmpQueryIds(int a, int b) {
	return queries[a].b > queries[b].b;
}

void solveQueries(int a, int b, int N, int M) {
	vector<int> queryIds;
	vector<int> blockedEdgesList;
	for(int i = a; i < b; ++i)
		if(!queries[i].update)
			queryIds.push_back(i);
	
	for(int i = a; i < b; ++i) { // Block edges
		if(queries[i].update) {
			blockedEdges[queries[i].a] = true;
			blockedEdgesList.push_back(queries[i].a);
		}
	}


	sort(queryIds.begin(), queryIds.end(), cmpQueryIds);
	// Sortam query-urile legite dupa w
	
	// pointer la ultima muchie updatata
	set<Edge>::iterator it = allEdges.begin();
	initDSU(N);
	for(auto query: queryIds) {
		while(it != allEdges.end() && it->w >= queries[query].b) {
			if(!blockedEdges[it->id]) {
				myunion(it->a, it->b);
			}
			it++;
		}

		for(int i = query - 1; i >= a; --i) {
			if(queries[i].update) {
				if(!bucketBlocked[queries[i].a]) {
					bucketBlocked[queries[i].a] = true;
					if(queries[i].b >= queries[query].b) {
						int sa = myfind(edges[queries[i].a].a), sb = myfind(edges[queries[i].a].b);

						graph[sa].push_back(sb);
						graph[sb].push_back(sa);
					}
				}
			}
		}
	
		for(auto it: blockedEdgesList)
			if(!bucketBlocked[it] && edges[it].w >= queries[query].b) {
				int sa = myfind(edges[it].a), sb = myfind(edges[it].b);
				graph[sa].push_back(sb);
				graph[sb].push_back(sa);
			}

		queries[query].rez = bfs(myfind(queries[query].a));
		undoDfs();

		for(auto it: blockedEdgesList) {
			int sa = myfind(edges[it].a), sb = myfind(edges[it].b);
			graph[sa].clear();
			graph[sb].clear();
		}

		for(int i = query - 1; i >= a; --i) {
			if(queries[i].update) {
				bucketBlocked[queries[i].a] = false;
				int sa = myfind(edges[queries[i].a].a), sb = myfind(edges[queries[i].a].b);

				graph[sa].clear();
				graph[sb].clear();
			}
		}
	}

	for(int i = a; i < b; ++i)
		if(queries[i].update) {
			allEdges.erase(edges[queries[i].a]);
			edges[queries[i].a].w = queries[i].b;
			allEdges.insert(edges[queries[i].a]);
			blockedEdges[queries[i].a] = false;
		}
}

int main() {
	int n, m, q;

	scanf("%d%d", &n, &m);
	
	for(int i = 1; i <= m; ++i) { // Read initial edges
		scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].w);

		edges[i].id = i;
		allEdges.insert(edges[i]);
	}

	scanf("%d", &q);

	for(int i = 0; i < q; ++i) { // Read queries
		int type;
		scanf("%d%d%d", &type, &queries[i].a, &queries[i].b);
		queries[i].update = (type == 1);
	}

	int iq = 0;
	while(iq < q) {
		int jq = iq, cntUpd = 0;
		while(jq < q && cntUpd < BUCK) {
			if(!queries[jq].update)
				++cntUpd;
			jq++;
		}

		solveQueries(iq, jq, n, m);
		
		iq = jq;
	}
	
	for(int i = 0; i < q; ++i)
		if(!queries[i].update)
			printf("%d\n", queries[i].rez);
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:172: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:175:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:181:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:185:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &type, &queries[i].a, &queries[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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