Submission #1259409

#TimeUsernameProblemLanguageResultExecution timeMemory
1259409dangkhoiUsmjeravanje (COCI22_usmjeravanje)C++20
0 / 110
0 ms320 KiB
#include<bits/stdc++.h> using namespace std; int x[200005],y[200005]; vector<int> order; vector<vector<int>> adj,adjr; bool vis[400005]; int str[400005]; int n,a,b,m; int cnt=0; void dfs1(int u){ vis[u]=1; for(int v:adj[u]) if(!vis[v]) dfs1(v); order.push_back(u); } void dfs2(int u){ str[u]=cnt; for(int v:adjr[u]) if(str[v]==-1) dfs2(v); } int sccount(){ adjr.assign(n+1,{}); for(int u=1;u<=n;u++){ for(int v:adj[u]) adjr[v].push_back(u); } order.clear(); for(int i=1;i<=n;i++) vis[i]=0; for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i); for(int i=1;i<=n;i++) str[i]=-1; cnt=0; for(int i=order.size()-1;i>=0;i--){ int u=order[i]; if(str[u]==-1){ dfs2(u); cnt++; } } return cnt; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); // freopen("ROAI.inp","r",stdin); // freopen("ROAI.out","w",stdout); cin>>a>>b>>m; for(int i=1;i<=m;i++) cin>>x[i]>>y[i]; n=a+b; int bscc=1e9,bmask=0; for(int mask=0;mask<(1<<m);mask++){ adj.assign(n+1,{}); for(int i=1;i<a;i++) adj[i].push_back(i+1); for(int i=a+1;i<n;i++) adj[i].push_back(i+1); for(int i=1;i<=m;i++){ if(mask&(1<<(i-1))) adj[a+y[i]].push_back(x[i]); else adj[x[i]].push_back(a+y[i]); } int scc=sccount(); if(scc<bscc){ bmask=mask; bscc=scc; } } cout<<bscc<<'\n'; for(int i=0;i<m;i++) cout<<((bmask>>i)&1)<<" "; cout<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...