oj.uz

답안 #196929

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
196929 2020-01-17T18:15:58 Z tincamatei 다리 (APIO19_bridges) C++14
46 / 100
 3000 ms 16416 KB 
#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 = 369;

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 dfs(int nod) {
	int sum = size[nod];
	
	viz[nod] = true;
	dfsStack.push_back(nod);

	for(auto it: graph[nod])
		if(!viz[it])
			sum += dfs(it);
	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 = dfs(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);
	}

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

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:161: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:164: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:170:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:174: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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 45 ms 1912 KB Output is correct
4 Correct 11 ms 1656 KB Output is correct
5 Correct 41 ms 1704 KB Output is correct
6 Correct 38 ms 1784 KB Output is correct
7 Correct 40 ms 1656 KB Output is correct
8 Correct 38 ms 1744 KB Output is correct
9 Correct 43 ms 1656 KB Output is correct
10 Correct 35 ms 1656 KB Output is correct
11 Correct 36 ms 1656 KB Output is correct
12 Correct 43 ms 1784 KB Output is correct
13 Correct 42 ms 1784 KB Output is correct
14 Correct 40 ms 1752 KB Output is correct
15 Correct 41 ms 1784 KB Output is correct
16 Correct 39 ms 1784 KB Output is correct
17 Correct 38 ms 1784 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2428 ms 8984 KB Output is correct
2 Correct 2712 ms 11856 KB Output is correct
3 Correct 2421 ms 12040 KB Output is correct
4 Correct 2256 ms 12008 KB Output is correct
5 Correct 2185 ms 11912 KB Output is correct
6 Correct 2559 ms 11528 KB Output is correct
7 Correct 2501 ms 11524 KB Output is correct
8 Correct 2607 ms 11564 KB Output is correct
9 Correct 87 ms 4600 KB Output is correct
10 Correct 1518 ms 10640 KB Output is correct
11 Correct 1436 ms 10512 KB Output is correct
12 Correct 1736 ms 10932 KB Output is correct
13 Correct 2073 ms 11748 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2070 ms 9336 KB Output is correct
2 Correct 977 ms 8100 KB Output is correct
3 Correct 2412 ms 13500 KB Output is correct
4 Correct 2594 ms 16416 KB Output is correct
5 Correct 87 ms 4600 KB Output is correct
6 Correct 2488 ms 14764 KB Output is correct
7 Correct 2514 ms 14656 KB Output is correct
8 Correct 2157 ms 13012 KB Output is correct
9 Correct 1612 ms 10556 KB Output is correct
10 Correct 1499 ms 10184 KB Output is correct
11 Correct 1800 ms 13988 KB Output is correct
12 Correct 1665 ms 12348 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3014 ms 11356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2428 ms 8984 KB Output is correct
2 Correct 2712 ms 11856 KB Output is correct
3 Correct 2421 ms 12040 KB Output is correct
4 Correct 2256 ms 12008 KB Output is correct
5 Correct 2185 ms 11912 KB Output is correct
6 Correct 2559 ms 11528 KB Output is correct
7 Correct 2501 ms 11524 KB Output is correct
8 Correct 2607 ms 11564 KB Output is correct
9 Correct 87 ms 4600 KB Output is correct
10 Correct 1518 ms 10640 KB Output is correct
11 Correct 1436 ms 10512 KB Output is correct
12 Correct 1736 ms 10932 KB Output is correct
13 Correct 2073 ms 11748 KB Output is correct
14 Correct 2070 ms 9336 KB Output is correct
15 Correct 977 ms 8100 KB Output is correct
16 Correct 2412 ms 13500 KB Output is correct
17 Correct 2594 ms 16416 KB Output is correct
18 Correct 87 ms 4600 KB Output is correct
19 Correct 2488 ms 14764 KB Output is correct
20 Correct 2514 ms 14656 KB Output is correct
21 Correct 2157 ms 13012 KB Output is correct
22 Correct 1612 ms 10556 KB Output is correct
23 Correct 1499 ms 10184 KB Output is correct
24 Correct 1800 ms 13988 KB Output is correct
25 Correct 1665 ms 12348 KB Output is correct
26 Execution timed out 3065 ms 14252 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 45 ms 1912 KB Output is correct
4 Correct 11 ms 1656 KB Output is correct
5 Correct 41 ms 1704 KB Output is correct
6 Correct 38 ms 1784 KB Output is correct
7 Correct 40 ms 1656 KB Output is correct
8 Correct 38 ms 1744 KB Output is correct
9 Correct 43 ms 1656 KB Output is correct
10 Correct 35 ms 1656 KB Output is correct
11 Correct 36 ms 1656 KB Output is correct
12 Correct 43 ms 1784 KB Output is correct
13 Correct 42 ms 1784 KB Output is correct
14 Correct 40 ms 1752 KB Output is correct
15 Correct 41 ms 1784 KB Output is correct
16 Correct 39 ms 1784 KB Output is correct
17 Correct 38 ms 1784 KB Output is correct
18 Correct 2428 ms 8984 KB Output is correct
19 Correct 2712 ms 11856 KB Output is correct
20 Correct 2421 ms 12040 KB Output is correct
21 Correct 2256 ms 12008 KB Output is correct
22 Correct 2185 ms 11912 KB Output is correct
23 Correct 2559 ms 11528 KB Output is correct
24 Correct 2501 ms 11524 KB Output is correct
25 Correct 2607 ms 11564 KB Output is correct
26 Correct 87 ms 4600 KB Output is correct
27 Correct 1518 ms 10640 KB Output is correct
28 Correct 1436 ms 10512 KB Output is correct
29 Correct 1736 ms 10932 KB Output is correct
30 Correct 2073 ms 11748 KB Output is correct
31 Correct 2070 ms 9336 KB Output is correct
32 Correct 977 ms 8100 KB Output is correct
33 Correct 2412 ms 13500 KB Output is correct
34 Correct 2594 ms 16416 KB Output is correct
35 Correct 87 ms 4600 KB Output is correct
36 Correct 2488 ms 14764 KB Output is correct
37 Correct 2514 ms 14656 KB Output is correct
38 Correct 2157 ms 13012 KB Output is correct
39 Correct 1612 ms 10556 KB Output is correct
40 Correct 1499 ms 10184 KB Output is correct
41 Correct 1800 ms 13988 KB Output is correct
42 Correct 1665 ms 12348 KB Output is correct
43 Execution timed out 3014 ms 11356 KB Time limit exceeded
44 Halted 0 ms 0 KB -