結果
問題 | No.3103 Butterfly Effect |
ユーザー |
![]() |
提出日時 | 2025-04-11 22:14:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,414 ms / 5,000 ms |
コード長 | 1,006 bytes |
コンパイル時間 | 4,342 ms |
コンパイル使用メモリ | 260,888 KB |
実行使用メモリ | 69,028 KB |
最終ジャッジ日時 | 2025-04-11 22:16:06 |
合計ジャッジ時間 | 53,262 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 50 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001LL int main(){ int n,q; cin>>n>>q; vector<int> p(q),x(q),y(q); vector<int> cur(n,Inf32); cur[0] = 0; int ans = 1; vector<set<pair<int,int>>> s(n); rep(i,q){ cin>>p[i]>>x[i]>>y[i]; x[i]--,y[i]--; queue<pair<int,int>> Q; if(cur[x[i]]<p[i]){ Q.emplace(x[i],p[i]); } if(cur[y[i]]<p[i]){ Q.emplace(y[i],p[i]); } s[x[i]].emplace(p[i],y[i]); s[y[i]].emplace(p[i],x[i]); while(Q.size()>0){ int t = Q.front().second,u = Q.front().first; Q.pop(); if(cur[u]==Inf32)ans++; cur[u] = min(cur[u],t); while(s[u].size()>0){ auto it = s[u].end(); it--; if((*it).first>cur[u]){ Q.emplace(it->second,it->first); s[u].erase(it); } else break; } } cout<<ans<<endl; } return 0; }