結果
問題 | No.2464 To DAG |
ユーザー |
![]() |
提出日時 | 2023-09-08 22:37:26 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,402 bytes |
コンパイル時間 | 2,134 ms |
コンパイル使用メモリ | 174,312 KB |
実行使用メモリ | 52,544 KB |
最終ジャッジ日時 | 2023-09-08 22:37:55 |
合計ジャッジ時間 | 27,863 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
8,760 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 258 ms
52,544 KB |
testcase_03 | AC | 571 ms
20,692 KB |
testcase_04 | AC | 464 ms
17,480 KB |
testcase_05 | AC | 426 ms
17,260 KB |
testcase_06 | AC | 388 ms
17,128 KB |
testcase_07 | AC | 392 ms
13,404 KB |
testcase_08 | AC | 430 ms
12,908 KB |
testcase_09 | AC | 359 ms
11,656 KB |
testcase_10 | AC | 346 ms
11,420 KB |
testcase_11 | AC | 257 ms
8,860 KB |
testcase_12 | AC | 193 ms
7,920 KB |
testcase_13 | AC | 221 ms
8,508 KB |
testcase_14 | AC | 382 ms
13,604 KB |
testcase_15 | AC | 439 ms
17,172 KB |
testcase_16 | AC | 231 ms
10,756 KB |
testcase_17 | AC | 37 ms
4,840 KB |
testcase_18 | AC | 153 ms
8,496 KB |
testcase_19 | AC | 2 ms
4,380 KB |
testcase_20 | AC | 1 ms
4,380 KB |
testcase_21 | AC | 2 ms
4,376 KB |
testcase_22 | AC | 152 ms
7,212 KB |
testcase_23 | AC | 145 ms
6,884 KB |
testcase_24 | AC | 159 ms
8,048 KB |
testcase_25 | AC | 156 ms
7,956 KB |
testcase_26 | AC | 107 ms
6,480 KB |
testcase_27 | AC | 595 ms
21,320 KB |
testcase_28 | AC | 620 ms
21,128 KB |
testcase_29 | AC | 602 ms
20,388 KB |
testcase_30 | AC | 532 ms
13,796 KB |
testcase_31 | AC | 512 ms
12,396 KB |
testcase_32 | AC | 496 ms
12,112 KB |
testcase_33 | AC | 385 ms
18,160 KB |
testcase_34 | AC | 188 ms
10,796 KB |
testcase_35 | TLE | - |
testcase_36 | TLE | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
ソースコード
#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; }