Submission #619921

#TimeUsernameProblemLanguageResultExecution timeMemory
619921errorgornNaboj (COCI22_naboj)C++17
110 / 110
464 ms44960 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ll long long #define ii pair<ll,ll> #define fi first #define se second #define endl '\n' #define puf push_front #define pof pop_front #define pub push_back #define pob pop_back #define lb lower_bound #define ub upper_bound #define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--)) #define all(x) (x).begin(),(x).end() #define sz(x) (int) (x).size() mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); int n,m; vector<ii> al[200005]; int in[200005]; int out[200005]; bool vis[200005]; vector<int> v; vector<ii> ans; signed main(){ cin.tie(0); cout.tie(0); cin.sync_with_stdio(false); cin>>n>>m; int a,b; rep(x,0,m){ cin>>a>>b; al[a].pub({b,0}); al[b].pub({a,1}); in[b]++; out[a]++; } rep(x,1,n+1) if (in[x]==0 || out[x]==0){ vis[x]=true; v.pub(x); } while (!v.empty()){ int u=v.back(); v.pob(); if (in[u]==0) ans.pub({u,1}); else ans.pub({u,0}); for (auto [it,x]:al[u]){ if (!vis[it]){ if (x==0) in[it]--; else out[it]--; if (in[it]==0 || out[it]==0){ vis[it]=true; v.pub(it); } } } } reverse(all(ans)); if (sz(ans)==n){ cout<<sz(ans)<<endl; for (auto [a,b]:ans) cout<<a<<" "<<b<<endl; } else{ cout<<"-1"<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...