結果
問題 | No.3103 Butterfly Effect |
ユーザー |
![]() |
提出日時 | 2025-02-12 01:54:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 573 ms / 5,000 ms |
コード長 | 1,142 bytes |
コンパイル時間 | 2,012 ms |
コンパイル使用メモリ | 206,836 KB |
実行使用メモリ | 61,116 KB |
最終ジャッジ日時 | 2025-02-12 03:14:44 |
合計ジャッジ時間 | 18,978 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 47 |
ソースコード
// fast // O(N + Q log Q) #include<bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q; cin >> n >> q; vector<int> dp(n, q+1); dp[0] = -1; vector<set<pair<int,int>>> horyu(n); int ans = 1; for (int num=0; num<q; num++) { int p; cin >> p; p--; int x, y; cin >> x >> y; x--; y--; if (dp[x] < p && dp[y] < p) { }else if (dp[x] > p && dp[y] > p) { horyu[x].insert(pair(p,y)); horyu[y].insert(pair(p,x)); }else{ if (dp[y] < p) { swap(x, y); } assert(dp[x] < p && dp[y] > p); if (dp[y] == q+1) ans++; dp[y] = p; priority_queue<pair<int,int>> mada; mada.push(pair(p,y)); while (!mada.empty()) { auto [t,i] = mada.top(); mada.pop(); if (dp[i] > t) continue; while (true) { auto itr = horyu[i].lower_bound(pair(t,0)); if (itr == horyu[i].end()) { break; } int tim = (*itr).first; int z = (*itr).second; horyu[i].erase(itr); if (dp[z] > tim) { if (dp[z] == q+1) ans++; dp[z] = tim; mada.push(pair(tim,z)); } } } } cout << ans << '\n'; } }