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