Submission #823826

#	Time	Username	Problem	Language	Result	Execution time	Memory
823826		Amylopectin	Stranded Far From Home (BOI22_island)	C++14	40 / 100	1105 ms	117576 KiB

island

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const long long mxn = 1e6 + 10;
// struct we
// {
//     long long noo,cva;
//     bool operator() (const struct we &l,const struct we &r)
//     {
//         return l.cva > r.cva;
//     }
// };
long long npop[mxn] = {},u[mxn] = {},bel[mxn] = {};
char ans[mxn] = {},wgr[mxn] = {};
// priority_queue<struct we,vector<struct we>,struct we> qu;
queue<long long> qu;
vector<long long> pat[mxn] = {},gr[mxn] = {},lli,poi[mxn] = {},cpoi
,upoi[mxn] = {};
long long re(long long cgr)
{
    long long i,j,fn,cn,cm,fm,fgr;
    wgr[cgr] = 1;
    for(i=0; i<gr[cgr].size(); i++)
    {
        cn = gr[cgr][i];
        ans[cn-1] = '1';
    }
    for(i=0; i<gr[cgr].size(); i++)
    {
        cn = gr[cgr][i];
        for(j=0; j<poi[cn].size(); j++)
        {
            fgr = poi[cn][j];
            if(wgr[fgr] == 0)
                re(fgr);
        }
    }
    for(i=0; i<upoi[cgr].size(); i++)
    {
        cn = bel[upoi[cgr][i]];
        if(wgr[cn] == 0)
        {
            re(cn);
        }
    }
    return 0;
}
int main()
{
    long long i,j,k,o,n,m,cn,cm,fn,fm,cou,cva,of,csi,gnu = 0;
    scanf("%lld %lld",&n,&m);
    for(i=1; i<=n; i++)
    {
        scanf("%lld",&npop[i]);
        of = 0;
        for(j=0; j<lli.size(); j++)
        {
            if(lli[j] == npop[i])
            {
                of = 1;
                break;
            }
        }
        if(of == 0)
        {
            lli.push_back(npop[i]);
        }
        ans[i-1] = '0';
    }
    sort(lli.begin(),lli.end());
    for(i=0; i<m; i++)
    {
        scanf("%lld %lld",&cn,&cm);
        pat[cn].push_back(cm);
        pat[cm].push_back(cn);
    }
    for(i=0; i<lli.size(); i++)
    {
        csi = lli[i];
        for(j=1; j<=n; j++)
        {
            if(u[j] != i+1 && npop[j] == csi)
            {
                qu.push(j);
                gr[gnu].push_back(j);
                bel[j] = gnu;
                u[j] = i+1;
                cpoi.clear();
                cva = 0;
                while(!qu.empty())
                {
                    cn = qu.front();
                    qu.pop();
                    cva += npop[cn];
                    for(k=0; k<pat[cn].size(); k++)
                    {
                        fn = pat[cn][k];
                        if(npop[fn] <= csi)
                        {
                            if(u[fn] != i+1)
                            {
                                qu.push(fn);
                                u[fn] = i+1;
                                if(npop[fn] == csi)
                                {
                                    gr[gnu].push_back(fn);
                                    bel[fn] = gnu;
                                }
                            }
                        }
                        else 
                        {
                            cpoi.push_back(fn);
                        }
                    }
                }
                for(k=0; k<cpoi.size(); k++)
                {
                    if(cva >= npop[cpoi[k]])
                    {
                        poi[cpoi[k]].push_back(gnu);
                        upoi[gnu].push_back(cpoi[k]);
                    }
                }
                gnu++;
            }
        }
    }
    re(gnu-1);
    // for(i=1; i<=n; i++)
    // {
    //     qu.push({i,npop[i]});
    //     u[i] = i;
    //     cou = 0;
    //     cva = 0;
    //     while(!qu.empty())
    //     {
    //         cn = qu.top().noo;
    //         qu.pop();
    //         if(cou > 0 && cva < npop[cn])
    //         {
    //             break;
    //         }
    //         cou ++;
    //         cva += npop[cn];
    //         for(j=0; j<pat[cn].size(); j++)
    //         {
    //             fn = pat[cn][j];
    //             if(u[fn] != i)
    //             {
    //                 qu.push({fn,npop[fn]});
    //                 u[fn] = i;
    //             }
    //         }
    //     }
    //     while(!qu.empty())
    //     {
    //         qu.pop();
    //     }
    //     if(cou == n)
    //     {
    //         ans[i-1] = '1';
    //     }
    //     else 
    //     {
    //         ans[i-1] = '0';
    //     }
    // }
    printf("%s\n",ans);
}

Compilation message (stderr)

island.cpp: In function 'long long int re(long long int)':
island.cpp:26:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(i=0; i<gr[cgr].size(); i++)
      |              ~^~~~~~~~~~~~~~~
island.cpp:31:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(i=0; i<gr[cgr].size(); i++)
      |              ~^~~~~~~~~~~~~~~
island.cpp:34:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(j=0; j<poi[cn].size(); j++)
      |                  ~^~~~~~~~~~~~~~~
island.cpp:41:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(i=0; i<upoi[cgr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
island.cpp:24:19: warning: unused variable 'fn' [-Wunused-variable]
   24 |     long long i,j,fn,cn,cm,fm,fgr;
      |                   ^~
island.cpp:24:25: warning: unused variable 'cm' [-Wunused-variable]
   24 |     long long i,j,fn,cn,cm,fm,fgr;
      |                         ^~
island.cpp:24:28: warning: unused variable 'fm' [-Wunused-variable]
   24 |     long long i,j,fn,cn,cm,fm,fgr;
      |                            ^~
island.cpp: In function 'int main()':
island.cpp:59:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(j=0; j<lli.size(); j++)
      |                  ~^~~~~~~~~~~
island.cpp:80:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(i=0; i<lli.size(); i++)
      |              ~^~~~~~~~~~~
island.cpp:98:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                     for(k=0; k<pat[cn].size(); k++)
      |                              ~^~~~~~~~~~~~~~~
island.cpp:120:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |                 for(k=0; k<cpoi.size(); k++)
      |                          ~^~~~~~~~~~~~
island.cpp:53:21: warning: unused variable 'o' [-Wunused-variable]
   53 |     long long i,j,k,o,n,m,cn,cm,fn,fm,cou,cva,of,csi,gnu = 0;
      |                     ^
island.cpp:53:36: warning: unused variable 'fm' [-Wunused-variable]
   53 |     long long i,j,k,o,n,m,cn,cm,fn,fm,cou,cva,of,csi,gnu = 0;
      |                                    ^~
island.cpp:53:39: warning: unused variable 'cou' [-Wunused-variable]
   53 |     long long i,j,k,o,n,m,cn,cm,fn,fm,cou,cva,of,csi,gnu = 0;
      |                                       ^~~
island.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%lld %lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
island.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%lld",&npop[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
island.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%lld %lld",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 30 / 30
• Subtask 5: 0 / 35