結果

問題 No.3639 Itsukin
コンテスト
ユーザー amesyu
提出日時 2026-08-25 14:40:07
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 542 ms / 2,000 ms
+ 522µs
コード長 1,540 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,527 ms
コンパイル使用メモリ 350,244 KB
実行使用メモリ 20,068 KB
最終ジャッジ日時 2026-08-25 14:40:29
合計ジャッジ時間 13,158 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サンプル 0 % AC * 1
小課題1 10 % AC * 6
小課題2 15 % AC * 5
小課題3 15 % AC * 16
小課題4 20 % AC * 10
小課題5 10 % AC * 15
小課題6 30 % AC * 35
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

struct UnionFind {
  std::vector<int> data;

  UnionFind() = default;

  explicit UnionFind(std::size_t sz) : data(sz, -1) {}

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (data[x] > data[y]) std::swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }

  int find(int k) {
    if (data[k] < 0) return (k);
    return data[k] = find(data[k]);
  }

  int size(int k) { return -data[find(k)]; }

  bool same(int x, int y) { return find(x) == find(y); }

  std::vector<std::vector<int>> groups() {
    int n = (int)data.size();
    std::vector<std::vector<int>> ret(n);
    for (int i = 0; i < n; i++) {
      ret[find(i)].emplace_back(i);
    }
    ret.erase(
        std::remove_if(ret.begin(), ret.end(),
                       [&](const std::vector<int>& v) { return v.empty(); }),
        ret.end());
    return ret;
  }
};

// これ好き
int main() {
	int n, m; cin >> n >> m;
	using Query = tuple<int, int, int, int>;
	vector<Query> events;
	for (int i = 0; i < m; ++i) {
		int u, v, l; cin >> u >> v >> l; --u; --v;
		events.push_back({l, 0, u, v});
	}
	int q; cin >> q;
	for (int qi = 0; qi < q; ++qi) {
		int p, t; cin >> p >> t; --t;
		events.push_back({p, 1, t, qi});
	}
	
	sort(events.begin(), events.end());
	UnionFind uf(n);
	vector<int> ans(q);

	for (auto [w, x, y, z] : events) {
		if (x == 0) {
			uf.unite(y, z);
		}
		if (x == 1) {
			ans[z] = uf.size(y);
		}
	}

	for (int a : ans) cout << a << endl;
}
0