# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
299071 | 2020-09-14T13:00:05 Z | MladenP | Planinarenje (COCI18_planinarenje) | C++17 | 5 ms | 1152 KB |
#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define lld long long #define pll pair<lld,lld> #define all(x) begin(x),end(x) #define mid ((l+r)/2) #define sz(x) int((x).size()) #define endl '\n' #define PRINT(x) cerr<<#x<<'='<<x<<endl #define INF 1000000000 #define pb push_back using namespace std; #define MAXN 5010 int N, M, matched[MAXN], pos[MAXN], with[MAXN]; vector<int> adj[MAXN]; bool dfs(int node) { //PRINT(node); pos[node] = true; for(auto x : adj[node]) { //PRINT(x); //PRINT(with[x]); if(with[x] == 0) { with[x] = node; matched[node] = x; return true; } else if(!pos[with[x]]) { bool tmp = dfs(with[x]); if(tmp) { with[x] = node; matched[node] = x; return true; } } } } int opt_matching() { for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) pos[j] = 0; bool nadjen = 0; for(int j = 1; j <= N; j++) { if(!matched[j] && !pos[j] && dfs(j)) nadjen = true; if(nadjen == true) break; } if(!nadjen) return i-1; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0); cin >> N >> M; for(int i = 1; i <= M; i++) { int x, y; cin >> x >> y; adj[x].pb(y); } int opt = opt_matching(); //PRINT(opt); //for(int i = 1; i <= N; i++) PRINT(matched[i]); for(int i = 1; i <= N; i++) pos[i] = 0; for(int i = 1; i <= N; i++) { if(!matched[i]) { cout << "Mirko\n"; continue; } else { PRINT(i); with[matched[i]] = 0; matched[i] = 0; for(int j = 1; j <= N; j++) pos[i] = 0; pos[i] = 1; bool nadjeno = false; for(int j = 1; j <= N; j++) { if(!pos[j] && !matched[j]) { PRINT(j); nadjeno = dfs(j); PRINT(nadjeno); } if(nadjeno) break; } //for(int i = 1; i <= N; i++) PRINT(matched[i]); if(nadjeno) { cout << "Mirko\n"; } else { cout << "Slavko\n"; for(int j = 1; j <= N; j++) pos[j] = 0; dfs(i); } } } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Runtime error | 1 ms | 768 KB | Execution killed with signal 11 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 768 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 768 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 768 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 3 ms | 1152 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 2 ms | 768 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 2 ms | 768 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 896 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 896 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 3 ms | 896 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |