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 |
|
|
|
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 |