제출 #233398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233398		alidoosti	Planinarenje (COCI18_planinarenje)	C++14	160 / 160	35 ms	768 KiB

planinarenje

#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 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16