Submission #605279

#	Time	Username	Problem	Language	Result	Execution time	Memory
605279		MohamedAliSaidane	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	1 ms	208 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
    using namespace std;

    typedef long long ll;

    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;

    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pii> vpi;
    typedef vector<pll> vpl;

    #define pb push_back
    #define popb pop_back
    #define all(x) (x).begin(),(x).end()


    vi p, rnk;
    int findset(int x){return p[x] = p[x] == x? x: findset(p[x]);}
    void unite(int i, int j)
    {
        int x= findset(i);
        int y = findset(j);
        if(x == y)
            return ;
        if(rnk[x] > rnk[y])
            swap(x,y);
        p[x] = y;
        if(rnk[x] == rnk[y])
            rnk[y] ++ ;
    }
    void solve(int l, int r, int cnt)
    {
        if(l == r)
            return ;
        int m = (l + r)/2;
        vi A, B;
        for(int i = l; i <= m; i ++)
            A.pb(i);
        for(int i = m + 1; i <= r; i ++)
            B.pb(i);
        int a = m - l + 1 > 1? use_machine(A): 0;
        int b = r - m > 1? use_machine(B): 0;
        if( a + b < cnt)
            unite(m, m + 1);
        solve(l, m, a);
        solve(m + 1, r, b);
        return ;
    }

    int count_mushrooms(int n)
    {
        p.resize(n);
        rnk.assign(n,0);
        for(int i = 0 ; i < n; i++)
            p[i] = i ;
        vi perm;
        for(int i=  0; i < n; i++)
            perm.pb(i);
        solve(0, n-1,use_machine(perm));
        int ans = 1 ;
        for(int i = 1; i < n;i ++)
        {
            if(findset(i) == findset(0))
                ans ++ ;
        }
        return ans;
    }
    /*
    int32_t main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0); cout.tie(0);
    }
    */

• Subtask 1: 0 / 100