Submission #773120


Source Code Expand

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <utility>
using namespace std;
int group[100000], num[100000];
int findgroup(int i) {
	return (i == group[i] ? i : group[i] = findgroup(group[i]));
}
void mergegroup(int i, int j) {
	i = findgroup(group[i]);
	j = findgroup(group[j]);
	if (i == j)	return;
	num[i] += num[j];	num[j] = 0;
	group[j] = group[i];
}
int main() {
	int n, m;	cin >> n >> m;
	vector<pair<int, pair<int, int> > > data;
	for (int i = 0; i < m; i++) {
		int a, b, y;	cin >> a >> b >> y;	a--;	b--;
		data.push_back(make_pair(y, make_pair(a, b)));
	}
	sort(data.begin(), data.end());
	reverse(data.begin(), data.end());
	int q;	cin >> q;
	vector<pair<int, pair<int,int> > > query(q);
	for (int i = 0; i < q; i++) {
		int v, w;	cin >> v >> w;	v--;
		query.push_back(make_pair(w, make_pair(v, i)));
	}
	sort(query.begin(), query.end());
	reverse(query.begin(), query.end());
	for (int i = 0; i < n; i++) {
		group[i] = i;
		num[i] = 1;
	}
	vector<int> ans(q,0);
	int edgeuse = 0;
	for (int i = 0; i < q; i++) {
		int t = query[i].first;
		while (edgeuse < data.size() && data[edgeuse].first > t) {
			int a = data[edgeuse].second.first;
			int b = data[edgeuse].second.second;
			a = findgroup(group[a]);
			b = findgroup(group[b]);
			mergegroup(a, b);
			edgeuse++;
		}
		int g = query[i].second.first;
		g = findgroup(group[g]);
		ans[query[i].second.second] = num[g];
	}
	for (int i = 0; i < q; i++)	cout << ans[i] << endl;
	return 0;
}

Submission Info

Submission Time
Task D - 道路の老朽化対策について
User fiord
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1548 Byte
Status AC
Exec Time 1997 ms
Memory 7408 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 50 / 50 50 / 50
Status
AC × 3
AC × 10
AC × 22
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Case Name Status Exec Time Memory
sample_01.txt AC 4 ms 256 KB
sample_02.txt AC 4 ms 256 KB
sample_03.txt AC 4 ms 256 KB
subtask1_01.txt AC 13 ms 384 KB
subtask1_02.txt AC 13 ms 384 KB
subtask1_03.txt AC 15 ms 384 KB
subtask1_04.txt AC 12 ms 256 KB
subtask1_05.txt AC 15 ms 384 KB
subtask1_06.txt AC 15 ms 384 KB
subtask1_07.txt AC 15 ms 384 KB
subtask2_01.txt AC 1071 ms 7280 KB
subtask2_02.txt AC 1083 ms 7280 KB
subtask2_03.txt AC 1048 ms 7280 KB
subtask2_04.txt AC 1066 ms 7280 KB
subtask2_05.txt AC 871 ms 5088 KB
subtask2_06.txt AC 995 ms 7408 KB
subtask2_07.txt AC 1036 ms 7408 KB
subtask2_08.txt AC 1043 ms 7408 KB
subtask2_09.txt AC 1088 ms 7280 KB
subtask2_10.txt AC 1058 ms 7280 KB
subtask2_11.txt AC 1070 ms 7152 KB
subtask2_12.txt AC 1997 ms 7152 KB