# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
240271 | 2020-06-19T06:01:20 Z | MrRobot_28 | Planinarenje (COCI18_planinarenje) | C++17 | 189 ms | 1064 KB |
#include<bits/stdc++.h> using namespace std; vector <vector <int> > g; vector <int> used, mat, mat1; bool dfs(int v, int cnt) { if(used[v] == cnt) { return false; } used[v] = cnt; for(int i = 0; i < g[v].size(); i++){ int to = g[v][i]; if(mat[to] == -1 || dfs(mat[to], cnt)) { mat[to] = v; return true; } } return false; } bool dfs1(int v, int cnt) { if(used[v] == cnt) { return false; } used[v] = cnt; for(int i = 0; i < g[v].size(); i++){ int to = g[v][i]; if(used[to] == cnt) { continue; } if(mat1[to] == -1 || dfs1(mat1[to], cnt)) { mat1[to] = v; return true; } } return false; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; cin >> n >> m; g.resize(2 * n); mat1.resize(2 * n ,-1); mat.resize(2 * n, -1); used.resize(2 * n); for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--; b--; b += n; g[a].push_back(b); g[b].push_back(a); } for(int i = 0;i < n; i++) { dfs(i, i + 1); } int cnt1 = 0; for(int i = n; i < n * 2; i++) { if(mat[i] != -1) { cnt1++; } } vector <bool> ans(n); for(int i = 0; i < n; i++) { int st = -1; for(int j = 0; j < 2 * n; j++){ mat1[j] = -1; } for(int j = 0; j < 2 * n; j++) { if(mat[j] != -1 && mat[j] != i) { mat1[mat[j]] = j; } if(mat[j] == i) { st = j; } } used[i] = n + i + 1; if(st != -1) { dfs1(st, n + i + 1); } int cnt2 = 0; for(int j = 0; j < n; j++) { if(mat1[j] != -1) { cnt2++; } } if(cnt1 == cnt2) { ans[i] = true; } else { ans[i] = false; } } for(int i = 0; i < n; i++) { if(ans[i]) { cout << "Mirco\n"; } else { cout << "Slavko\n"; } } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Incorrect | 5 ms | 384 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 288 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 189 ms | 1064 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 24 ms | 512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 29 ms | 640 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 44 ms | 760 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 70 ms | 768 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |