Submission #1799154
Source Code Expand
#include <iostream>
#include <algorithm>
#include <array>
#include <cstdint>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <vector>
#define INF 1000000000
#define MOD 1000000007
#define ll long long
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define bitget(a,b) (((a) >> (b)) & 1)
#define vint vector<int>
#define ALL(x) (x).begin(),(x).end()
#define C(x) cout << #x << " : " << x << endl
using int32 = int_fast32_t;
using int64 = int_fast64_t;
using uint32 = uint_fast32_t;
using uint64 = uint_fast64_t;
using namespace std;
class UnionFind {
public:
std::vector<int32> tree;
//コンストラクタ
UnionFind(size_t size) :tree(size, -1) {}
//xの代表ノード
int32 find(int32 &x) {
if (tree[x] < 0) return x;
return tree[x] = find(tree[x]);
}
//x,yを要素に持つ2集合の併合
void unite(int32 x, int32 y) {
x = find(x);
y = find(y);
if (x == y) return;
if (tree[x] > tree[y]) {
tree[y] += tree[x];
tree[x] = y;
}
else {
tree[x] += tree[y];
tree[y] = x;
}
return;
}
//xを要素に持つ集合の要素数
size_t size(int32 x) {
return -tree[find(x)];
}
//x,yが同じ集合に属しているか
bool same(int32 &x, int32 &y) {
return find(x) == find(y);
}
};
int main() {
int i, j, k;
int32 n, m, q;
scanf("%d %d", &n, &m);
vector<pair<int, pair<int, int>>>edge(m);
int a, b, y;
rep(i, 0, m) {
scanf("%d %d %d", &a, &b, &y);
edge[i] = make_pair(y, make_pair(a, b));
}
scanf("%d", &q);
vector<pair<int, pair<int, int>>>query(q);
int v, w;
rep(i, 0, q) {
scanf("%d %d", &v, &w);
query[i] = make_pair(w, make_pair(v, i));
}
sort(edge.begin(), edge.end());
sort(query.begin(), query.end());
int ans[100002];
int now = m - 1;
UnionFind x(n + 2);
int t1, t2;
for (i = q - 1; i > -1; i--) {
if (now != -1) {
while (edge[now].first > query[i].first) {
x.unite(edge[now].second.first, edge[now].second.second);
now--;
if (now == -1)
break;
}
}
ans[query[i].second.second] = x.size(query[i].second.first);
}
rep(i, 0, q)
printf("%d\n", ans[i]);
return 0;
}
Submission Info
Submission Time
2017-11-23 13:34:58+0900
Task
D - 道路の老朽化対策について
User
noshi91
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
2272 Byte
Status
AC
Exec Time
104 ms
Memory
5504 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:68:23: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘int32* {aka long int*}’ [-Wformat=]
scanf("%d %d", &n, &m);
^
./Main.cpp:68:23: warning: format ‘%d’ expects argument of type ‘int*’, but argument 3 has type ‘int32* {aka long int*}’ [-Wformat=]
./Main.cpp:75:16: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘int32* {aka long int*}’ [-Wformat=]
scanf("%d", &q);
^
./Main.cpp:68:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
^
./Main.cpp:72:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &a, &b, &y);
^
./Main.cpp:75:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, decl...
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
2 ms
256 KB
subtask1_02.txt
AC
2 ms
256 KB
subtask1_03.txt
AC
2 ms
256 KB
subtask1_04.txt
AC
2 ms
256 KB
subtask1_05.txt
AC
2 ms
256 KB
subtask1_06.txt
AC
2 ms
256 KB
subtask1_07.txt
AC
2 ms
256 KB
subtask2_01.txt
AC
102 ms
5376 KB
subtask2_02.txt
AC
103 ms
5376 KB
subtask2_03.txt
AC
103 ms
5376 KB
subtask2_04.txt
AC
104 ms
5376 KB
subtask2_05.txt
AC
54 ms
3840 KB
subtask2_06.txt
AC
98 ms
5504 KB
subtask2_07.txt
AC
100 ms
5504 KB
subtask2_08.txt
AC
100 ms
5504 KB
subtask2_09.txt
AC
104 ms
5376 KB
subtask2_10.txt
AC
104 ms
5376 KB
subtask2_11.txt
AC
104 ms
5248 KB
subtask2_12.txt
AC
102 ms
5120 KB