Submission #1259409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259409		dangkhoi	Usmjeravanje (COCI22_usmjeravanje)	C++20	0 / 110	0 ms	320 KiB

Main

#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';
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60