제출 #196945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
196945		tincamatei	다리 (APIO19_bridges)	C++14	30 / 100	3031 ms	11208 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 = 320;

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();
}

int allEdges[MAX_M];
bool blockedEdges[1+MAX_M];
bool bucketBlocked[1+MAX_M];

bool cmpEdgeIds(int a, int b) {
	return edges[a].w > edges[b].w;
}

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
	sort(allEdges, allEdges + M, cmpEdgeIds);
	int it = 0;
	initDSU(N);
	for(auto query: queryIds) {
		while(it < M && edges[allEdges[it]].w >= queries[query].b) {
			if(!blockedEdges[allEdges[it]]) {
				myunion(edges[allEdges[it]].a, edges[allEdges[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) {
			edges[queries[i].a].w = queries[i].b;
			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[i - 1] = 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);
	}

	for(int i = 0; i < q; i += BUCK)
		solveQueries(i, min(q, i + BUCK), n, m);

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

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'int main()':
bridges.cpp:175: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:178: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:184:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:188: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: 17 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27