Submission #222849

#	Time	Username	Problem	Language	Result	Execution time	Memory
222849		bensonlzl	Planinarenje (COCI18_planinarenje)	C++14	160 / 160	25 ms	1024 KiB

planinarenje

#include <bits/stdc++.h>

using namespace std;

vector<vector<int> > AdjList, BackList;
vector<int> P, visited;
vector<pair<int,int> > matches;
int label[5005], match = 0, N, M, p, v;

bool Aug(int x) {
  	if (visited[x]) return 0;
    visited[x] = 1;
    for (auto it:AdjList[x]) {
        if (P[it] == -1) {
            P[it] = x;
            return 1;
        }
    }
    for (auto it:AdjList[x]) {
        if (Aug(P[it])) {
            P[it] = x;
            return 1;
        }
    }
    return 0;
}

void BackAug(int x){
	visited[x] = 1;
	label[x] = 0;
	for (auto it : AdjList[x])
		if (!visited[P[it]]) BackAug(P[it]);
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	AdjList.resize(N+1); BackList.resize(N+1); visited.resize(N+1);	P.resize(N+1,-1);
  	for (int i = 1; i <= M; ++i){
  		cin >> p >> v;
  		AdjList[p].push_back(v), BackList[v].push_back(p);
  	}
    for (int i = 1; i <= N; ++i) {
        visited.resize(N+1, 0);
        match += Aug(i);
        visited.clear();
    }
    for (int i = 1; i <= N; ++i) 
        if (P[i] != -1) matches.emplace_back(P[i], i);
    for (auto it : matches)
    	label[it.first] = 1;
    for (int i = 1; i <= N; ++i){
    	if (!label[i]){
    		visited.resize(N+1, 0);
    		BackAug(i);
    		visited.clear();
    	}
    }
    for (int i = 1; i <= N; ++i){
    	if (!label[i]) cout << "Mirko\n";
    	else cout << "Slavko\n";
    }
}

• 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