제출 #978605

#제출 시각아이디문제언어결과실행 시간메모리
978605bebraPlaninarenje (COCI18_planinarenje)C++17
144 / 160
1067 ms852 KiB
#include <bits/stdc++.h> using namespace std; #define dbg(x) cerr << #x << ": " << x << endl; const int MAX_N = 5000 + 5; vector<int> g[MAX_N]; int used[MAX_N]; int match[MAX_N]; int timer = 0; bool dfs(int v) { if (used[v] == timer) { return false; } used[v] = timer; for (auto u : g[v]) { if (match[u] == -1) { match[u] = v; return true; } } for (auto u : g[v]) { if (dfs(match[u])) { match[u] = v; return true; } } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; --u, --v; g[u].push_back(v); } memset(match, -1, sizeof(match)); int cnt = 0; for (int v = 0; v < n; ++v) { ++timer; cnt += dfs(v); } for (int i = 0; i < n; ++i) { int curr = 0; memset(match, -1, sizeof(match)); for (int v = 0; v < n; ++v) { if (v == i) continue; ++timer; curr += dfs(v); } if (curr < cnt) { cout << "Slavko\n"; } else { cout << "Mirko\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...