結果
問題 |
No.416 旅行会社
|
ユーザー |
|
提出日時 | 2022-11-04 14:15:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 342 ms / 4,000 ms |
コード長 | 3,366 bytes |
コンパイル時間 | 1,574 ms |
コンパイル使用メモリ | 145,900 KB |
最終ジャッジ日時 | 2025-02-08 17:09:09 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <queue> #include <string> #include <map> #include <set> #include <stack> #include <tuple> #include <deque> #include <array> #include <numeric> #include <bitset> #include <iomanip> #include <cassert> #include <chrono> #include <random> #include <limits> #include <iterator> #include <functional> #include <sstream> #include <fstream> #include <complex> #include <cstring> #include <unordered_map> #include <unordered_set> using namespace std; // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") // #pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl") using ll = long long; constexpr int INF = 1001001001; constexpr int mod = 1000000007; // constexpr int mod = 998244353; template<class T> inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template<class T> inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}; constexpr int dy[] = {0, 1, 0, -1, 1, -1, 1, -1}; struct PartiallyPersistentUnionFind { vector<int> data; vector<int> last; vector<vector<pair<int, int>>> history; PartiallyPersistentUnionFind() = default; PartiallyPersistentUnionFind(int sz){ data.resize(sz, -1); last.resize(sz, 1e+9); history.resize(sz); for(auto& vs : history) vs.emplace_back(-1, -1); } int find(int t, int x){ if(t < last[x]) return x; return find(t, data[x]); } bool same(int t, int x, int y){ return find(t, x) == find(t, y); } bool unite(int t, int x, int y){ x = find(t, x); y = find(t, y); if(x == y) return false; if(data[x] > data[y]) swap(x, y); data[x] += data[y]; history[x].emplace_back(t, data[x]); data[y] = x; last[y] = t; return true; } int size(int t, int x){ x = find(t, x); return -prev(lower_bound(begin(history[x]), end(history[x]), make_pair(t, 0))) -> second; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, Q; cin >> N >> M >> Q; vector<int> A(M), B(M), C(Q), D(Q); for(int i = 0; i < M; ++i){ cin >> A[i] >> B[i]; --A[i], --B[i]; } set<pair<int, int>> destroy_bridge; for(int i = 0; i < Q; ++i){ cin >> C[i] >> D[i]; --C[i], --D[i]; destroy_bridge.emplace(C[i], D[i]); } for(int i = 0; i < M; ++i){ if(destroy_bridge.count(make_pair(A[i], B[i]))) continue; C.emplace_back(A[i]); D.emplace_back(B[i]); } reverse(begin(C), end(C)); reverse(begin(D), end(D)); PartiallyPersistentUnionFind uf(N); for(int i = 0; i < M; ++i){ uf.unite(i, C[i], D[i]); } vector<int> ans(N, -1); for(int i = 1; i < N; ++i){ int ng = -1, ok = M; while(ok - ng > 1){ int m = (ng + ok) / 2; (uf.same(m, 0, i) ? ok : ng) = m; } ans[i] = M - ok; if(ans[i] > Q) ans[i] = -1; } for(int i = 1; i < N; ++i){ cout << ans[i] << '\n'; } return 0; }