Submission #227368

#TimeUsernameProblemLanguageResultExecution timeMemory
227368mohammad_aminPlaninarenje (COCI18_planinarenje)C++14
160 / 160
40 ms3072 KiB
#include <bits/stdc++.h> using namespace std; const int MN = 50012; vector <int> adj[MN], kaj[MN]; int p[MN]; bool mark[MN]; int good[MN]; bool dfs(int v) { mark[v] = true; for (int u: adj[v]) { if ((p[u] == -1) || (!mark[p[u]] && dfs(p[u]))) { p[u] = v; return true; } } return false; } bool kfs(int v) { // cerr << v << endl; mark[v] = true; for (int u: kaj[v]) { // cerr << v << ' ' << u << ' ' << good[u] << endl; if ((good[u] == -1) || (!mark[good[u]] && kfs(good[u]))) { // cerr << v << '?' << u << '?' << good[u] << endl; return true; } } return false; } int main() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) good[i] = p[i] = -1; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; adj[--a].push_back(--b); kaj[b].push_back(a); } for (int i = 0; i < n; i++) { for (int i = 0; i < n; i++) mark[i] = false; dfs(i); } // good[2] = -1; // cerr << (good[2] = -1) << '*' << endl; for (int i = 0; i < n; i++) if (p[i] != -1) good[p[i]] = i;//, cerr << p[i] << '=' << i << endl; // for (int i = 0; i < n; i++) // cerr << p[i] << '!' << ' '; // cerr << endl; // for (int i = 0; i < n; i++) // cerr << good[i] << '!' << ' '; // cerr << endl; for (int i = 0; i < n; i++) { for (int i = 0; i < n; i++) mark[i] = false; if (good[i] == -1) cout << "Mirko\n"; else if (kfs(good[i])) cout << "Mirko\n"; else cout << "Slavko\n"; } }
#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...