Submission #437397

#TimeUsernameProblemLanguageResultExecution timeMemory
437397mammedbrkPlaninarenje (COCI18_planinarenje)C++14
48 / 160
7 ms1996 KiB
#include<bits/stdc++.h> #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 5e4+10; bool mark[maxn], fmatch[maxn], tmp[maxn]; vector<int> adj[maxn]; int match[maxn]; bool dfs(int v){ if(mark[v]) return false; mark[v] = true; for(int u: adj[v]) if(match[u] == -1 || dfs(match[u])){ match[u] = v; return true; } return false; } bool dfs2(int v){ if(mark[v]) return true; mark[v] = true; for(int u: adj[v]) if(dfs2(match[u])){ tmp[match[u]] = false; return true; } return false; } int main(){ memset(match, -1, sizeof(match)); int n, m; cin >> n >> m; for(int i = 0, u, v; i < m; i++){ cin >> u >> v; u--; v--; adj[u].pb(v); } bool find = true; while(find){ find = false; memset(mark, 0, sizeof(mark)); for(int i = 0; i < n; i++) if(!fmatch[i] && dfs(i)){ find = true; fmatch[i] = true; } } memset(mark, 0, sizeof(mark)); memset(tmp, 1, sizeof(tmp)); for(int i = 0; i < n; i++) if(!fmatch[i]) dfs2(i); for(int i = 0; i < n; i++) if(!fmatch[i] || !tmp[i]) cout << "Mirko\n"; else cout << "Slavko\n"; 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...