AtCoder Beginner Contest 040

Submission #773120

Source codeソースコード

#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

Task問題 D - 道路の老朽化対策について
User nameユーザ名 fiord
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1548 Byte
File nameファイル名
Exec time実行時間 1997 ms
Memory usageメモリ使用量 7408 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
Subtask1 50 / 50 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 50 / 50 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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