結果
問題 | No.2464 To DAG |
ユーザー |
![]() |
提出日時 | 2023-09-08 22:37:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,402 bytes |
コンパイル時間 | 1,962 ms |
コンパイル使用メモリ | 176,968 KB |
実行使用メモリ | 52,608 KB |
最終ジャッジ日時 | 2024-06-26 15:50:33 |
合計ジャッジ時間 | 31,557 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 35 TLE * 4 |
ソースコード
#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<vector<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; for(auto x:vec[now]) { if(del[x.second]||check_edge[x.second]) continue; ll k=dfs(x.first); if(k>=0) { del[x.second]=true; if(k!=now) { this_sec[now]=false; return k; } } else check_edge[x.second]=true; } 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<vector<pair<ll,ll>>> (N+100,vector<pair<ll,ll>> (0)); del=vector<bool> (M+100); check=vector<bool> (N+100); check_edge=vector<bool> (M+100); this_sec=vector<bool> (N+100); for(ll i=0;i<M;i++) { ll U,V;cin>>U>>V; U--;V--; vec[U].push_back(make_pair(V,i)); } for(ll i=0;i<N;i++) { ll k=dfs(i); } vector<pair<ll,ll>> ans(0); for(ll i=0;i<N;i++) { for(auto x:vec[i]) { if(del[x.second]) continue; ans.push_back(make_pair(i+1,x.first+1)); } } cout<<N<<" "<<(ll)ans.size()<<endl; for(auto x:ans) cout<<x.first<<" "<<x.second<<endl; }