oj.uz

Submission #440652

# Submission time Handle Problem Language Result Execution time Memory
440652 2021-07-02T16:13:14 Z Parisa Planinarenje (COCI18_planinarenje) C++17
160 / 160
 16 ms 4492 KB 
#include<bits/stdc++.h>
#include<string>
using namespace std;
#define S second
#define F first
#define pb push_back
#define MP make_pair
#define ll long long
#define PAIR pair <ll ,ll >
#define reversee(x) reverse(x.begin(), x.end());
#define sortt(x) sort(x.begin(), x.end());
#define flash ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define cout(l) cout<<fixed<<setprecision(10)<<l;
const ll maxn=1e5+10, mod=1e9+7 , inf=2e9 , lg=20;
ll mark[maxn] , match[maxn] , fmatch[maxn];
vector<ll> adj[maxn];
bool dfs(ll v){
    mark[v]=1;
    for(auto u:adj[v]){
        if(match[u]==-1 || (!mark[match[u]] && dfs(match[u]))) {
            match[u]=v;
            fmatch[v]=1;
            return 1;
        }

    }
    return 0;
}
int main(){
    ll n , m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        ll x, y;
        cin>>x>>y;
        x-- , y--;
        adj[x].pb(y);

    }
    memset(match , -1 , sizeof(match));
    bool flag=1;
    while(flag){
        flag=0;
        memset(mark , 0 , sizeof(mark));
        for(int i=0;i<n;i++){
            if(!fmatch[i] && !mark[i] && dfs(i)){
                flag=1;

            }
        }
    }
    for(int i=0;i<n;i++){
        if(!fmatch[i] ){
            dfs(i);
        }
    }
    for(int i=0;i<n;i++){
        if(mark[i]) cout<<"Mirko"<<endl;
        else cout<<"Slavko"<<endl;
    }

}

Subtask #1
16.0 / 16.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4424 KB Output is correct
2 Correct 15 ms 4492 KB Output is correct
3 Correct 15 ms 4460 KB Output is correct
4 Correct 16 ms 4488 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4172 KB Output is correct
2 Correct 6 ms 4332 KB Output is correct
3 Correct 5 ms 4172 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4172 KB Output is correct
2 Correct 6 ms 4372 KB Output is correct
3 Correct 5 ms 4172 KB Output is correct
4 Correct 7 ms 4300 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4312 KB Output is correct
2 Correct 15 ms 4332 KB Output is correct
3 Correct 10 ms 4384 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4300 KB Output is correct
2 Correct 12 ms 4400 KB Output is correct
3 Correct 8 ms 4300 KB Output is correct
4 Correct 7 ms 4300 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4344 KB Output is correct
2 Correct 8 ms 4300 KB Output is correct
3 Correct 13 ms 4300 KB Output is correct
4 Correct 8 ms 4300 KB Output is correct