結果
問題 | No.3103 Butterfly Effect |
ユーザー |
![]() |
提出日時 | 2025-04-11 22:49:13 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,445 ms / 5,000 ms |
コード長 | 4,907 bytes |
コンパイル時間 | 7,318 ms |
コンパイル使用メモリ | 333,332 KB |
実行使用メモリ | 112,416 KB |
最終ジャッジ日時 | 2025-04-11 22:50:14 |
合計ジャッジ時間 | 54,261 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 50 |
ソースコード
#include <bits/stdc++.h> #if __has_include(<atcoder/all>) #include <atcoder/all> std::istream &operator>>(std::istream &is, atcoder::modint &v) { long long value; is >> value; v = value; return is; } std::ostream &operator<<(std::ostream &os, const atcoder::modint &v) { os << v.val(); return os; } std::ostream &operator<<(std::ostream &os, const atcoder::modint998244353 &v) { os << v.val(); return os; } std::istream &operator>>(std::istream &is, atcoder::modint998244353 &v) { long long x; is >> x; v = x; return is; } std::ostream &operator<<(std::ostream &os, const atcoder::modint1000000007 &v) { os << v.val(); return os; } std::istream &operator>>(std::istream &is, atcoder::modint1000000007 &v) { long long x; is >> x; v = x; return is; } #endif using namespace std; using ll = long long; using lint = __int128_t; using pll = pair<ll, ll>; #define newl '\n'; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) #define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--) #define all(x) begin(x), end(x) #define SZ(x) ll(x.size()) #define eb emplace_back #define pb push_back #define TT template <typename T> TT using vec = vector<T>; TT using vvec = vec<vec<T>>; TT using vvvec = vec<vvec<T>>; TT using minheap = priority_queue<T, vector<T>, greater<T>>; TT using maxheap = priority_queue<T>; TT bool chmin(T &x, T y) { return x > y ? (x = y, true) : false; } TT bool chmax(T &x, T y) { return x < y ? (x = y, true) : false; } TT T smod(T x, T mod) { x %= mod; if (x < 0) x += mod; return x; } TT bool rng(T l, T x, T r) { return l <= x && x < r; } TT T flr(T a, T b) { if (b < 0) a = -a, b = -b; return a >= 0 ? a / b : (a + 1) / b - 1; } TT T cil(T a, T b) { if (b < 0) a = -a, b = -b; return a > 0 ? (a - 1) / b + 1 : a / b; } TT T sqr(T x) { return x * x; } //{0, 1, ... } -> {p[0], p[1], ...} template <typename T, typename S> void rearrange(vector<T> &A, vector<S> const &p) { assert(p.size() == A.size()); vector<T> a = A; for (int i = 0; i < ssize(A); ++i) { a[i] = A[p[i]]; } swap(a, A); } template <typename T, typename S, typename... Ts> void rearrange(vector<T> &A, vector<S> p, vector<Ts> &...rest) { rearrange(A, p); (rearrange(rest, p), ...); } template <typename T, typename Compare, typename... Ts> void rearrange(vector<T> &A, Compare cmp, vector<Ts> &...rest) { vector<int> p(ssize(A)); iota(p.begin(), p.end(), 0); sort(p.begin(), p.end(), cmp); rearrange(A, p); (rearrange(rest, p), ...); } struct io_setup { io_setup() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); } } io_setup; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << p.first << " " << p.second; return os; } TT ostream &operator<<(ostream &os, const vector<T> &v) { for (size_t i = 0; i < v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template <typename T, size_t n> ostream &operator<<(ostream &os, const array<T, n> &v) { for (size_t i = 0; i < n; i++) { os << v[i] << (i + 1 != n ? " " : ""); } return os; } template <typename T> ostream &operator<<(ostream &os, const vvec<T> &v) { for (size_t i = 0; i < v.size(); i++) { os << v[i] << (i + 1 != v.size() ? "\n" : ""); } return os; } TT istream &operator>>(istream &is, vector<T> &v) { for (size_t i = 0; i < v.size(); i++) { is >> v[i]; } return is; } #if __has_include(<debug/debug.hpp>) #include <debug/debug.hpp> #else #define dbg(...) true #define DBG(...) true #define OUT(...) true #endif const ll inf = LLONG_MAX / 4; int main() { ll n, q; cin >> n >> q; vector<ll> know(n, inf); know[0] = -1; vector qs(n, set<pll>()); ll ans = 1; // vから伸びる辺であって、時刻 [t, ) で最初を見る auto dfs = [&](auto f, int v, ll t) -> void { if (know[v] > t) return; auto it = qs[v].lower_bound(pll(t, -1)); while (it != qs[v].end()) { auto [p, tar] = *it; if (know[tar] == inf) ans++; if (chmin(know[tar], p)) { f(f, tar, p + 1); it++; continue; } else { qs[v].erase(it++); } } }; rep(i, 0, q) { ll p, x, y; cin >> p >> x >> y; p--, x--, y--; qs[x].insert(pll(p, y)); qs[y].insert(pll(p, x)); dfs(dfs, x, p); dfs(dfs, y, p); cout << ans << endl; } } /* 同じ議論を繰り返さない do smth instead of nothing and stay organized WRITE STUFF DOWN DON'T GET STUCK ON ONE APPROACH */