Submission #1308333
Source Code Expand
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
struct UnionFind{
vector<int> data;
UnionFind(int size) : data(size, -1){}
bool unionSet(int x, int y){
x = root(x);
y = root(y);
if (x != y){
if (data[y] < data[x]) swap(x, y);
data[x] += data[y];
data[y] = x;
}
return x != y;
}
bool findSet(int x, int y) {return root(x) == root(y);}
int root(int x) {return data[x] < 0 ? x : data[x] = root(data[x]);}
int size(int x) {return -data[root(x)];}
};
int main() {
int N, M;
cin >> N >> M;
vector<tuple<int, int, int>> yab;
for (int m = 0; m != M; ++m){
int a, b, y;
cin >> a >> b >> y;
yab.emplace_back(make_tuple(y, a - 1, b - 1));
}
sort(yab.begin(), yab.end());
int Q;
cin >> Q;
vector<tuple<int, int, int>> wvq;
for (int q = 0; q != Q; ++q){
int v, w;
cin >> v >> w;
wvq.emplace_back(make_tuple(w, v - 1, q));
}
sort(wvq.begin(), wvq.end(), greater<>());
UnionFind uf(N);
vector<int> ans(Q, 0);
for (auto &wvqi : wvq){
int w, v, q;
tie(w, v, q) = wvqi;
while(not yab.empty()){
int y, a, b;
tie(y, a, b) = yab.back();
if (y <= w) break;
uf.unionSet(a, b);
yab.pop_back();
}
ans[q] = uf.size(v);
}
for (auto a : ans) cout << a << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 道路の老朽化対策について |
User |
rpy3cpp |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1580 Byte |
Status |
AC |
Exec Time |
419 ms |
Memory |
6512 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 |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
5 ms |
256 KB |
subtask1_02.txt |
AC |
5 ms |
256 KB |
subtask1_03.txt |
AC |
5 ms |
256 KB |
subtask1_04.txt |
AC |
4 ms |
256 KB |
subtask1_05.txt |
AC |
5 ms |
256 KB |
subtask1_06.txt |
AC |
5 ms |
256 KB |
subtask1_07.txt |
AC |
5 ms |
256 KB |
subtask2_01.txt |
AC |
400 ms |
5744 KB |
subtask2_02.txt |
AC |
403 ms |
5744 KB |
subtask2_03.txt |
AC |
413 ms |
5744 KB |
subtask2_04.txt |
AC |
413 ms |
5744 KB |
subtask2_05.txt |
AC |
293 ms |
3700 KB |
subtask2_06.txt |
AC |
372 ms |
6256 KB |
subtask2_07.txt |
AC |
390 ms |
6512 KB |
subtask2_08.txt |
AC |
395 ms |
5872 KB |
subtask2_09.txt |
AC |
416 ms |
5744 KB |
subtask2_10.txt |
AC |
416 ms |
6128 KB |
subtask2_11.txt |
AC |
419 ms |
5616 KB |
subtask2_12.txt |
AC |
418 ms |
5488 KB |