ICPC DHAKA REGIONAL PRELIMINARY CONTEST, 2019

B. The Social Network

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

#define mx 100005
typedef vector <int> VI;

int n, q;
int par[mx];
VI tmp[mx];
bitset <mx> mark;

int fnd(int u) {
    if (par[u] == u) return u;
    return par[u] = fnd(par[u]);
}

int main() {
//    freopen("../templates/in", "r", stdin);
    int tc; scanf("%d", &tc);
    int t = 0;
    while (tc--) {
        mark = 0;
        scanf("%d %d",&n, &q);
        for (int i = 1; i <= n; i++) {
            par[i] = i;
            tmp[i].clear();
        }

        printf("Case %d:\n", ++t);
        while (q--) {
            int c; scanf("%d", &c);
            if (c == 0) {
                int u, v; scanf("%d %d", &u, &v);
                int pu = fnd(u);
                int pv = fnd(v);
                if (pu == pv) continue;
                if (tmp[pu].size() > tmp[pv].size()) {
                    swap(pu, pv);
                }

                for (auto x : tmp[pu]) tmp[pv].push_back(x);
                par[pu] = pv;
                mark[pv] = 1;
            } else if (c == 1) {
                int u, T;
                scanf("%d %d", &u, &T);
                int pu = fnd(u);
                tmp[pu].push_back(T);
                mark[pu] = 1;
            } else {
                int u, l, r;
                scanf("%d %d %d", &u, &l, &r);
                int pu = fnd(u);
                int ans = 0;
                if (mark[pu]) {
                    sort(tmp[pu].begin(), tmp[pu].end());
                    mark[pu] = 0;
                }

                auto lt = lower_bound(tmp[pu].begin(), tmp[pu].end(), l);
                auto rt = upper_bound(tmp[pu].begin(), tmp[pu].end(), r);

                if (rt > lt) ans = rt - lt;
                printf("%d\n", ans);
            }
        }
    }
}

C. ICGeSi Standings

#include<bits/stdc++.h>

using namespace std;

main()

{

    int ts,cs=1;

    scanf("%d",&ts);

    while(ts--)

    {

        int n,ns[75]= {0},tp[75]= {0},frozen[75][75]= {0},flag=0,i,j,fro_solve[75]= {0};

        scanf("%d",&n);

        int a,b,c,m;

        for(i=1; i<=n; i++)

        {

            scanf("%d%d%d",&a,&b,&c);

            ns[a]=b;

            tp[a]=c;

            scanf("%d",&m);

            fro_solve[a]=m;

            for(j=1; j<=m; j++)

            {

                scanf("%d", &frozen[a][j]);

            }

        }

        int rnk;

        for(i=1; i<=n; i++)

        {

            cin>>rnk;

            int n_s, t_p;

            if(i==1)

            {

                ns[rnk]+=fro_solve[rnk];

                for(j=1; j<=fro_solve[rnk]; j++)

                {

                    tp[rnk]+=frozen[rnk][j];

                }

                n_s=ns[rnk];

                t_p=tp[rnk];

            }

            else

            {

                if(n_s>=ns[rnk])

                {

                    if(n_s==ns[rnk]&&t_p>tp[rnk])

                    {

                        flag=1;

                    }

                }

                else

                {

                    flag=1;

                }

                for(j=1; j<=fro_solve[rnk]; j++)

                {

                    if(n_s>=ns[rnk])

                    {

                        if(n_s==ns[rnk]&&t_p>tp[rnk])

                        {

                            flag=1;

                            break;

                        }

                        else

                        {

                            if(n_s-1>ns[rnk])

                            {

                                tp[rnk]+=frozen[rnk][j];

                                ns[rnk]+=1;

                            }

                            else if((n_s>ns[rnk])&&(t_p<=(tp[rnk]+frozen[rnk][j])))

                            {

                                tp[rnk]+=frozen[rnk][j];

                                ns[rnk]+=1;

                            }

                            else

                            {

                                break;

                            }

                        }

                    }

                    else

                    {

                        flag=1;

                        break;

                    }

                }

                n_s=ns[rnk];

                t_p=tp[rnk];

            }

        }

        if(flag==0)

        {

            printf("Case %d: We respect our judges :)\n",cs++);

        }

        else

        {

            printf("Case %d: Say no to rumour >:\n",cs++);

        }

    }

}

B. The Social Network

#include<bits/stdc++.h>

using namespace std;

#define max 10000007

int phi[max],sz=10000001;

long long com[max];

void phi_calc()

{

    int  i,j,cnt=0;

    for(i=2; i<max; i++)

    {

        if(phi[i]==0)

        {

            phi[i]=i-1;

            for(j=i*2; j<max; j=j+i)

            {

                cnt++;

                if(phi[j]==0)

                {

                    phi[j]=j;

                }

                phi[j]=phi[j]-(phi[j]/i);

            }

        }

    }

    unsigned   long long s,d=0;

    com[1]=1;

    for(s=2; s<max; s++)

    {

        com[s]=com[s-1]+(long long)phi[s];

    }

}

main()

{

    phi_calc();

    int ts,cs=1;

    scanf("%d",&ts);

    while(ts--)

    {

        long long n;

        long long p;

        scanf("%lld%lld",&n,&p);

        long long  ind=lower_bound(com,com+sz,p)-com;

        long long ans=n/ind;

        if(ans==0)

            ans=-1;

        printf("Case %d: %lld\n",cs++,ans);

    }

}