oj.uz

답안 #823826

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
823826 2023-08-13T07:56:23 Z Amylopectin Stranded Far From Home (BOI22_island) C++14
40 / 100
 1000 ms 117576 KB 
#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 94156 KB Output is correct
2 Correct 46 ms 94204 KB Output is correct
3 Correct 45 ms 94232 KB Output is correct
4 Correct 70 ms 97892 KB Output is correct
5 Correct 52 ms 94672 KB Output is correct
6 Correct 53 ms 94396 KB Output is correct
7 Correct 67 ms 97544 KB Output is correct
8 Correct 67 ms 98812 KB Output is correct
9 Correct 46 ms 94324 KB Output is correct
10 Correct 49 ms 94548 KB Output is correct
11 Correct 51 ms 94468 KB Output is correct
12 Correct 49 ms 94444 KB Output is correct
13 Correct 45 ms 94396 KB Output is correct
14 Correct 48 ms 94408 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 94156 KB Output is correct
2 Correct 44 ms 94156 KB Output is correct
3 Execution timed out 1105 ms 95216 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 94172 KB Output is correct
2 Execution timed out 1097 ms 95304 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 94164 KB Output is correct
2 Correct 311 ms 116460 KB Output is correct
3 Correct 295 ms 116464 KB Output is correct
4 Correct 287 ms 117576 KB Output is correct
5 Correct 163 ms 108548 KB Output is correct
6 Correct 153 ms 108208 KB Output is correct
7 Correct 140 ms 110816 KB Output is correct
8 Correct 113 ms 109672 KB Output is correct
9 Correct 166 ms 110584 KB Output is correct
10 Correct 156 ms 108608 KB Output is correct
11 Correct 216 ms 113472 KB Output is correct

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 94156 KB Output is correct
2 Correct 46 ms 94204 KB Output is correct
3 Correct 45 ms 94232 KB Output is correct
4 Correct 70 ms 97892 KB Output is correct
5 Correct 52 ms 94672 KB Output is correct
6 Correct 53 ms 94396 KB Output is correct
7 Correct 67 ms 97544 KB Output is correct
8 Correct 67 ms 98812 KB Output is correct
9 Correct 46 ms 94324 KB Output is correct
10 Correct 49 ms 94548 KB Output is correct
11 Correct 51 ms 94468 KB Output is correct
12 Correct 49 ms 94444 KB Output is correct
13 Correct 45 ms 94396 KB Output is correct
14 Correct 48 ms 94408 KB Output is correct
15 Correct 45 ms 94156 KB Output is correct
16 Correct 44 ms 94156 KB Output is correct
17 Execution timed out 1105 ms 95216 KB Time limit exceeded
18 Halted 0 ms 0 KB -