結果
問題 | No.2464 To DAG |
ユーザー |
![]() |
提出日時 | 2023-09-08 22:46:54 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 637 ms / 2,000 ms |
コード長 | 1,475 bytes |
コンパイル時間 | 2,168 ms |
コンパイル使用メモリ | 186,452 KB |
実行使用メモリ | 86,528 KB |
最終ジャッジ日時 | 2024-06-26 16:02:12 |
合計ジャッジ時間 | 23,757 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll =int; #define all(v) v.begin(),v.end() #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) vector<set<pair<ll,ll>>> vec; vector<bool> del; vector<bool> this_sec; vector<bool> check; vector<bool> check_edge; ll dfs(ll now) { if(this_sec[now]) { return now; } if(check[now]) return -1; this_sec[now]=true; vector<pair<ll,ll>> no; for(auto x:vec[now]) { no.push_back(x); ll k=dfs(x.first); if(k>=0) { del[x.second]=true; if(k!=now) { for(auto y:no) vec[now].erase(y); this_sec[now]=false; return k; } } else check_edge[x.second]=true; } for(auto y:no) vec[now].erase(y); check[now]=true; this_sec[now]=false; return -1LL; } int main() { ios::sync_with_stdio(false); cin.tie(0); ll N,M;cin>>N>>M; vec=vector<set<pair<ll,ll>>> (N+100); del=vector<bool> (M+100); check=vector<bool> (N+100); check_edge=vector<bool> (M+100); this_sec=vector<bool> (N+100); vector<tuple<ll,ll,ll>> memo(M); for(ll i=0;i<M;i++) { ll U,V;cin>>U>>V; U--;V--; vec[U].insert(make_pair(V,i)); memo[i]=make_tuple(U,V,i); } for(ll i=0;i<N;i++) { ll k=dfs(i); } vector<pair<ll,ll>> ans(0); for(auto x:memo) { if(del[get<2>(x)]) continue; ans.push_back(make_pair(get<0>(x),get<1>(x))); } cout<<N<<" "<<(ll)ans.size()<<endl; for(auto x:ans) cout<<x.first+1<<" "<<x.second+1<<endl; }