結果
問題 | No.3103 Butterfly Effect |
ユーザー |
![]() |
提出日時 | 2025-04-11 22:10:55 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 717 ms / 5,000 ms |
コード長 | 2,203 bytes |
コンパイル時間 | 3,649 ms |
コンパイル使用メモリ | 314,424 KB |
実行使用メモリ | 100,300 KB |
最終ジャッジ日時 | 2025-04-11 22:11:23 |
合計ジャッジ時間 | 23,739 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 50 |
ソースコード
#include<bits/stdc++.h> namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include<atcoder/all> #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; constexpr long long INF = 1002003004005006007; vector<long long> dijkstra(const auto& to, int s = 0) { struct QueElem { int v; long long d; bool operator<(const QueElem& a) const { return d > a.d; } QueElem(int v, long long d) : v(v), d(d) {} }; priority_queue<QueElem> q; vector<long long> dist(to.size(), INF); dist[s] = 0; q.emplace(s, 0); while (!q.empty()) { auto [u, d] = q.top(); q.pop(); if (d > dist[u]) continue; for (auto [v, dv] : to[u]) { long long nd = max<ll>(d, dv); if (nd < dist[v]) { dist[v] = nd; q.emplace(v, nd); } } } return dist; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector<tuple<int, int, int>> es(q); rep(i, q) { int p, x, y; cin >> p >> x >> y; p--, x--, y--; es[p] = {x, y, i}; } VI v_tail(n); rep(i, n) v_tail[i] = i; vector<vector<P>> to(n); int nxt = n; rep(p, q) { auto [x, y, i] = es[p]; int px = v_tail[x], py = v_tail[y]; int nx = nxt++, ny = nxt++; v_tail[x] = nx, v_tail[y] = ny; rep(_, 2) to.emplace_back(); to[px].emplace_back(nx, 0); to[py].emplace_back(ny, 0); to[nx].emplace_back(ny, i); to[ny].emplace_back(nx, i); } auto dist = dijkstra(to, 0); VI ans(q); rep(x, n) { int v = v_tail[x]; if (dist[v] < q) ans[dist[v]]++; } rep(i, q - 1) ans[i+1] += ans[i]; for (int x : ans) cout << x << '\n'; }