답안 #95793 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95793	2019-02-02T15:56:36 Z	Bodo171	무지개나라 (APIO17_rainbow)	C++14	11 / 100	3000 ms	359268 KB

rainbow

#include "rainbow.h"
#include <fstream>
#include <iostream>
#include <map>
#include <vector>
#define mp make_pair
using namespace std;
const int nmax=200005;
int d1[]={-1,0,1,0};
int d2[]={0,-1,0,1};
map< pair<int,int>,int > rb,norm;
vector<int> ad[10*nmax];
pair<int,int> v[nmax];
int viz[10*nmax];
int n,nr,mnl=2*nmax,mnc=2*nmax,mxl,mxc;
void add_rainbow(int l,int c)
{
    if(!rb[mp(l,c)]) v[++n]={l,c};
    rb[mp(l,c)]=1;
    mnl=min(mnl,l);
    mxl=max(mxl,l);
    mnc=min(mnc,c);
    mxc=max(mxc,c);
}
void add(int l,int c)
{
    int p;
    if((!norm[mp(l,c)])&&(!rb[mp(l,c)]))
        {
            norm[mp(l,c)]=++nr;
            for(int dir=0;dir<4;dir++)
            {
                p=norm[mp(l+d1[dir],c+d2[dir])];
                if(p)
                    ad[p].push_back(nr),ad[nr].push_back(p);
            }
        }
}
void init(int R, int C, int sr, int sc, int M, char *S) {
    add_rainbow(sr,sc);
    for(int i=0;i<M;i++)
    {
        if(S[i]=='N')
            sr--;
        if(S[i]=='S')
            sr++;
        if(S[i]=='W')
           sc--;
        if(S[i]=='E')
          sc++;
        add_rainbow(sr,sc);

    }
}
void dfs(int x)
{
    viz[x]=1;
    for(int i=0;i<ad[x].size();i++)
        if(!viz[ad[x][i]])
          dfs(ad[x][i]);
}
int colour(int ar, int ac, int br, int bc) {
    int cc=0;
    nr=0;
    for(int i=1;i<=n;i++)
        for(int p1=-1;p1<=1;p1++)
          for(int p2=-1;p2<=1;p2++)
            if(v[i].first+p1>=ar&&v[i].first+p1<=br&&v[i].second+p2>=ac&&v[i].second+p2<=bc)
          add(v[i].first+p1,v[i].second+p2);
    if(!(ar<mnl&&mxl<br&&ac<mnc&&mxc<bc))
    {
        for(int i=ar; i<=br; i++)
            add(i,ac),add(i,bc);
        for(int i=ac; i<=bc; i++)
            add(ar,i),add(br,i);
    }
     for(int i=1;i<=nr;i++)
        if(!viz[i])
          dfs(i),cc++;
    norm.clear();
    for(int i=1;i<=nr;i++)
        ad[i].clear(),viz[i]=0;
    return cc;
}

Compilation message

rainbow.cpp: In function 'void dfs(int)':
rainbow.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ad[x].size();i++)
                 ~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	81 ms	47480 KB	Output is correct
2	Correct	217 ms	47608 KB	Output is correct
3	Correct	126 ms	47608 KB	Output is correct
4	Correct	142 ms	47600 KB	Output is correct
5	Correct	272 ms	47736 KB	Output is correct
6	Correct	44 ms	47224 KB	Output is correct
7	Correct	43 ms	47352 KB	Output is correct
8	Correct	46 ms	47352 KB	Output is correct
9	Correct	44 ms	47352 KB	Output is correct
10	Correct	45 ms	47224 KB	Output is correct
11	Correct	242 ms	47580 KB	Output is correct
12	Correct	368 ms	47736 KB	Output is correct
13	Correct	463 ms	47736 KB	Output is correct
14	Correct	613 ms	47864 KB	Output is correct
15	Correct	43 ms	47352 KB	Output is correct
16	Correct	44 ms	47352 KB	Output is correct
17	Correct	44 ms	47352 KB	Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	43 ms	47352 KB	Output is correct
2	Correct	1288 ms	172024 KB	Output is correct
3	Correct	1269 ms	172024 KB	Output is correct
4	Correct	1182 ms	162588 KB	Output is correct
5	Correct	580 ms	109308 KB	Output is correct
6	Correct	1362 ms	206024 KB	Output is correct
7	Correct	238 ms	57436 KB	Output is correct
8	Correct	131 ms	60152 KB	Output is correct
9	Correct	95 ms	56056 KB	Output is correct
10	Correct	77 ms	51320 KB	Output is correct
11	Correct	171 ms	64676 KB	Output is correct
12	Correct	391 ms	89416 KB	Output is correct
13	Correct	389 ms	89308 KB	Output is correct
14	Correct	338 ms	89336 KB	Output is correct
15	Correct	329 ms	87524 KB	Output is correct
16	Correct	1016 ms	174996 KB	Output is correct
17	Correct	1182 ms	165496 KB	Output is correct
18	Correct	1500 ms	210500 KB	Output is correct
19	Correct	1608 ms	221316 KB	Output is correct
20	Correct	1379 ms	178048 KB	Output is correct
21	Correct	331 ms	77304 KB	Output is correct
22	Correct	364 ms	75640 KB	Output is correct
23	Correct	566 ms	117880 KB	Output is correct
24	Correct	892 ms	150776 KB	Output is correct
25	Correct	912 ms	111924 KB	Output is correct
26	Correct	820 ms	111752 KB	Output is correct
27	Execution timed out	3026 ms	359268 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #4
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	81 ms	47480 KB	Output is correct
2	Correct	217 ms	47608 KB	Output is correct
3	Correct	126 ms	47608 KB	Output is correct
4	Correct	142 ms	47600 KB	Output is correct
5	Correct	272 ms	47736 KB	Output is correct
6	Correct	44 ms	47224 KB	Output is correct
7	Correct	43 ms	47352 KB	Output is correct
8	Correct	46 ms	47352 KB	Output is correct
9	Correct	44 ms	47352 KB	Output is correct
10	Correct	45 ms	47224 KB	Output is correct
11	Correct	242 ms	47580 KB	Output is correct
12	Correct	368 ms	47736 KB	Output is correct
13	Correct	463 ms	47736 KB	Output is correct
14	Correct	613 ms	47864 KB	Output is correct
15	Correct	43 ms	47352 KB	Output is correct
16	Correct	44 ms	47352 KB	Output is correct
17	Correct	44 ms	47352 KB	Output is correct
18	Execution timed out	3060 ms	75336 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	81 ms	47480 KB	Output is correct
2	Correct	217 ms	47608 KB	Output is correct
3	Correct	126 ms	47608 KB	Output is correct
4	Correct	142 ms	47600 KB	Output is correct
5	Correct	272 ms	47736 KB	Output is correct
6	Correct	44 ms	47224 KB	Output is correct
7	Correct	43 ms	47352 KB	Output is correct
8	Correct	46 ms	47352 KB	Output is correct
9	Correct	44 ms	47352 KB	Output is correct
10	Correct	45 ms	47224 KB	Output is correct
11	Correct	242 ms	47580 KB	Output is correct
12	Correct	368 ms	47736 KB	Output is correct
13	Correct	463 ms	47736 KB	Output is correct
14	Correct	613 ms	47864 KB	Output is correct
15	Correct	43 ms	47352 KB	Output is correct
16	Correct	44 ms	47352 KB	Output is correct
17	Correct	44 ms	47352 KB	Output is correct
18	Execution timed out	3060 ms	75336 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

답안 #95793

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 0 / 12.0

Subtask #3 0 / 24.0

Subtask #4 0 / 27.0

Subtask #5 0 / 26.0

Subtask #1
11.0 / 11.0

Subtask #2
0 / 12.0

Subtask #3
0 / 24.0

Subtask #4
0 / 27.0

Subtask #5
0 / 26.0