oj.uz

Submission #233397

# Submission time Handle Problem Language Result Execution time Memory
233397 2020-05-20T11:38:29 Z alidoosti Planinarenje (COCI18_planinarenje) C++14
48 / 160
 7 ms 768 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 5e3 + 12;
int n, m;
int par[N], vis[N], loc;
vector <int> ad[N];
string ans[2] = {"Slavko\n", "Mirko\n"};

void init();
void solve();
bool dfs(int);

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	init();
	solve();
	return 0;
}


void init() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		ad[v].push_back(u);
	}
	return;
}

void solve() {
	for (int i = 0; i < N; i++) par[i] = -1;
	for (int i = 0; i < n; i++) {
		loc = i + 1;
		dfs(i);
	}
	for (int i = 0; i < n; i++) {
		int val = 0;
		if (par[i] == -1) val = 1;
		else {
			loc = n + 1 + i;
			vis[i] = loc;
			if (dfs(par[i])) {
				par[i] = -1;
				val = 1;
			}
		}
		cout << ans[val];
	}
	return;
}

bool dfs(int root) {
	for (auto x : ad[root]) {
		if (vis[x] == loc) continue;
		vis[x] = loc;
		if (par[x] == -1) {
			par[x] = root;
			return 1;
		}
	}

	for (auto x : ad[root]) {
		if (vis[x] == loc) continue;
		vis[x] = loc;
		if (dfs(par[x])) {
			par[x] = root;
			return 1;
		}
	}
	return 0;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 768 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 7 ms 768 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -