Submission #436992

#TimeUsernameProblemLanguageResultExecution timeMemory
436992mostafaPlaninarenje (COCI18_planinarenje)C++14
160 / 160
11 ms672 KiB
// in the name of GOD++ #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define mpp make_pair #define pb push_back #define F first #define S second //#pragma GCC optimize("O2") const int MX=5e3+10; vector<int> adj[MX]; bool match1[MX]; int match2[MX]; bool mrk[MX]; bool dfs(int v) { mrk[v]=1; if(!adj[v].size()) return 0; for(int u:adj[v]){ if(!match2[u]){ match1[v]=1; match2[u]=v; return 1; } } for(int u:adj[v]){ if(!mrk[match2[u]]&&dfs(match2[u])){ match1[v]=1; match2[u]=v; return 1; } } return 0; } bool ans[MX]; void solve(int v) { mrk[v]=1; ans[v]=1; for(int u:adj[v]){ if(!mrk[match2[u]]) solve(match2[u]); } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; for(int i=0;i<m;i++){ int v,u; cin>>v>>u; adj[v].pb(u); } int fnd=1; while(fnd){ fnd=0; fill(mrk,mrk+n+2,0); for(int i=1;i<=n;i++){ if((!mrk[i])&&(!match1[i])&&dfs(i)){ fnd=1; } } } fill(mrk,mrk+n+2,0); for(int i=1;i<=n;i++){ if(match1[i]==0){ fill(mrk,mrk+n+2,0); solve(i); } } for(int i=1;i<=n;i++){ if(ans[i]) cout<<"Mirko"<<endl; else cout<<"Slavko"<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...