oj.uz

Submission #200164

# Submission time Handle Problem Language Result Execution time Memory
200164 2020-02-05T15:12:08 Z Saboon Planinarenje (COCI18_planinarenje) C++14
160 / 160
 22 ms 764 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 5000 + 37;

int match[maxn], fmatch[maxn];
vector<int> g[maxn];
bool visited[maxn];

bool dfs(int v){
	if (v == 0 or visited[v] == true)
		return false;
	visited[v] = true;
	for (auto u : g[v]){
		if (match[u] == -1 or dfs(match[u])){
			match[u] = v;
			fmatch[v] = u;
			return true;
		}
	}
	return false;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		int v, u;
		cin >> v >> u;
		g[u].push_back(v);
	}
	memset(fmatch, -1, sizeof fmatch);
	memset(match, -1, sizeof match);
	for (int i = 1; i <= n; i++){
		memset(visited, 0, sizeof visited);
		dfs(i);
	}
	for (int i = 1; i <= n; i++){
		if (match[i] == -1){
			cout << "Mirko\n";
			continue;
		}
		int v = match[i];
		fmatch[match[i]] = -1;
		match[i] = 0;
		memset(visited, 0, sizeof visited);
		if (dfs(v)){
			cout << "Mirko\n";
			match[i] = -1;
			continue;
		}
		cout << "Slavko\n";
	}
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 508 KB Output is correct
4 Correct 5 ms 504 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 636 KB Output is correct
2 Correct 9 ms 760 KB Output is correct
3 Correct 8 ms 664 KB Output is correct
4 Correct 8 ms 632 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 632 KB Output is correct
2 Correct 18 ms 632 KB Output is correct
3 Correct 7 ms 632 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 8 ms 632 KB Output is correct
4 Correct 14 ms 632 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 632 KB Output is correct
2 Correct 12 ms 764 KB Output is correct
3 Correct 7 ms 632 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 632 KB Output is correct
2 Correct 8 ms 760 KB Output is correct
3 Correct 7 ms 520 KB Output is correct
4 Correct 22 ms 632 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 760 KB Output is correct
2 Correct 8 ms 632 KB Output is correct
3 Correct 8 ms 632 KB Output is correct
4 Correct 16 ms 632 KB Output is correct