oj.uz

Submission #233398

# Submission time Handle Problem Language Result Execution time Memory
233398 2020-05-20T11:54:33 Z alidoosti Planinarenje (COCI18_planinarenje) C++14
160 / 160
 35 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;
		}
		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
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 #3
16.0 / 16.0

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

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 6 ms 640 KB Output is correct
2 Correct 6 ms 672 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 6 ms 640 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 512 KB Output is correct
2 Correct 16 ms 640 KB Output is correct
3 Correct 9 ms 512 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 11 ms 512 KB Output is correct
4 Correct 13 ms 640 KB Output is correct

Subtask #8
16.0 / 16.0

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

Subtask #9
16.0 / 16.0

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

Subtask #10
16.0 / 16.0

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