oj.uz

Submission #436290

# Submission time Handle Problem Language Result Execution time Memory
436290 2021-06-24T11:35:43 Z MahlaEn Planinarenje (COCI18_planinarenje) C++17
160 / 160
 13 ms 3304 KB 
#include<bits/stdc++.h>
#define pb          push_back
#define vec         vector
#define ub          upper_bound
#define lb          lower_bound
#define per         next_permutation
#define itn         int
#define sc          second
#define fr          first
#define FOR(i,l,r)  for(int i=l;i<=r;i++)
#define RFOR(i,r,l) for(int i=r;i>=l;i--)
#define IOS         ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define all(x)      x.begin(), x.end()
#define rall(c)     (c).rend(), (c).rbegin
#define kill(x)     return cout << x << endl, 0
#define SZ(x)       int(x.size())
#define it          iterator
#define mp          make_pair
#define BPT(n)      pow(2,floor(log2((n))));
#define LPT(n)      pow(2,ceil(log2((n))*1.0));
#define endl        "\n"
#define dbg(x) {cerr<<#x<<" = "<<x<<'\n';}
#define dbgp(x) {cerr<<#x<<" : {"<<x.fr<<", "<<x.sc<<"}\n";}
#define dbgv(x) {cerr<<#x<<" : "; for(int i:x) cerr<<i<<' '; cerr<<'\n';}
#define dbga(x, l, r) {cerr<<#x<<' '<<l<<"..."<<r<<" : "; for(int i=l; i<r; i++) cerr<<x[i]<<' '; cerr<<'\n';}
using namespace std;
typedef long long       ll;
typedef long double     ld;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;
typedef pair <pii, pii> ppp;
typedef pair <ll, ll>   pll;
/* Reverse Iterate on Set A sintax
    for( set<int>::reverse_iterator i = A.rbegin() ; i!=A.rend() ; i++){
        cout << *i <<' ';
    }
*/
ll pw(ll base,ll e){
    return e?pw(base*base,e/2)*(e%2?base:1):1;
}
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
//Converts s string to int
ll to_int(string s){
    ll ret = 0;
    FOR(i,0,s.size()){
        ret += pw(10,s.size()-i-1) * (ll)(s[i] - '0');
    }
    return ret;
}
const int maxn=1e5+10,mod=1e9+7;
const ll INF=1e9;
vec<int>e[maxn];
bitset<maxn>fmatch,mark;
int match[maxn];
bitset<maxn>win;
bool dfs(int cur){
    mark[cur]=1;
    win[cur]=1;
    for(int i:e[cur]){
        if(match[i]==-1 ||(!mark[match[i]] && dfs(match[i]))){
            match[i]=cur;
            return 1;
        }
    }
    return 0;
}
int main(){
    memset(match,-1,sizeof(match));
    int n,m,u,v;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>u>>v;
        u--;v--;
        e[u].pb(v);
    }
    bool find=1;
    while(find){
        find=0;
        mark.reset();
        for(int i=0;i<n;i++){
            if(!fmatch[i]){
                if(dfs(i)){
                    fmatch[i]=1;
                    find=1;
                }
            }
        }
    }
    // cout<<fmatch.count();
    win.reset();
    for(int i=0;i<n;i++){
        if(!fmatch[i]){
            mark.reset();
            dfs(i);
        }
    }
    // kill("ok");
    for(int i=0;i<n;i++){
        if(win[i]){
            cout<<"Mirko\n";
            continue;
        }
        else{
            cout<<"Slavko\n";
        }
    }
}

Compilation message

planinarenje.cpp: In function 'll to_int(std::string)':
planinarenje.cpp:10:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define FOR(i,l,r)  for(int i=l;i<=r;i++)
......
   48 |     FOR(i,0,s.size()){
      |         ~~~~~~~~~~~~              
planinarenje.cpp:48:5: note: in expansion of macro 'FOR'
   48 |     FOR(i,0,s.size()){
      |     ^~~

Subtask #1
16.0 / 16.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3304 KB Output is correct
2 Correct 7 ms 3184 KB Output is correct
3 Correct 9 ms 3276 KB Output is correct
4 Correct 9 ms 3276 KB Output is correct

Subtask #6
16.0 / 16.0

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

Subtask #7
16.0 / 16.0

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

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3192 KB Output is correct
2 Correct 13 ms 3208 KB Output is correct
3 Correct 8 ms 3176 KB Output is correct

Subtask #9
16.0 / 16.0

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

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3148 KB Output is correct
2 Correct 7 ms 3180 KB Output is correct
3 Correct 8 ms 3148 KB Output is correct
4 Correct 6 ms 3148 KB Output is correct