oj.uz

Submission #222849

# Submission time Handle Problem Language Result Execution time Memory
222849 2020-04-14T08:30:40 Z bensonlzl Planinarenje (COCI18_planinarenje) C++14
160 / 160
 25 ms 1024 KB 
#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.0 / 16.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1024 KB Output is correct
2 Correct 25 ms 1024 KB Output is correct
3 Correct 22 ms 1024 KB Output is correct
4 Correct 22 ms 1024 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 7 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 8 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 640 KB Output is correct
2 Correct 23 ms 1024 KB Output is correct
3 Correct 10 ms 768 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 14 ms 896 KB Output is correct
3 Correct 10 ms 640 KB Output is correct
4 Correct 7 ms 640 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 944 KB Output is correct
2 Correct 10 ms 640 KB Output is correct
3 Correct 13 ms 896 KB Output is correct
4 Correct 7 ms 640 KB Output is correct