답안 #95794 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95794	2019-02-02T16:01:58 Z	Bodo171	무지개나라 (APIO17_rainbow)	C++14	35 / 100	3000 ms	359032 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((!rb[mp(l,c)])&&(!norm[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);
            }
        }
}
int lim;
void init(int R, int C, int sr, int sc, int M, char *S) {
    add_rainbow(sr,sc);
    lim=max(R,C);
    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++;
    if(lim<=50)
    {
        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:60: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	86 ms	47328 KB	Output is correct
2	Correct	215 ms	47612 KB	Output is correct
3	Correct	130 ms	47480 KB	Output is correct
4	Correct	148 ms	47612 KB	Output is correct
5	Correct	231 ms	47720 KB	Output is correct
6	Correct	43 ms	47352 KB	Output is correct
7	Correct	46 ms	47352 KB	Output is correct
8	Correct	43 ms	47352 KB	Output is correct
9	Correct	44 ms	47352 KB	Output is correct
10	Correct	45 ms	47352 KB	Output is correct
11	Correct	209 ms	47568 KB	Output is correct
12	Correct	283 ms	47608 KB	Output is correct
13	Correct	477 ms	48012 KB	Output is correct
14	Correct	470 ms	47736 KB	Output is correct
15	Correct	45 ms	47224 KB	Output is correct
16	Correct	44 ms	47352 KB	Output is correct
17	Correct	47 ms	47224 KB	Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	47224 KB	Output is correct
2	Correct	1266 ms	172116 KB	Output is correct
3	Correct	1241 ms	172148 KB	Output is correct
4	Correct	1154 ms	162784 KB	Output is correct
5	Correct	613 ms	109560 KB	Output is correct
6	Correct	1347 ms	205944 KB	Output is correct
7	Correct	141 ms	55416 KB	Output is correct
8	Correct	129 ms	60160 KB	Output is correct
9	Correct	97 ms	55936 KB	Output is correct
10	Correct	75 ms	51192 KB	Output is correct
11	Correct	169 ms	64676 KB	Output is correct
12	Correct	386 ms	89328 KB	Output is correct
13	Correct	355 ms	89208 KB	Output is correct
14	Correct	359 ms	89336 KB	Output is correct
15	Correct	341 ms	87544 KB	Output is correct
16	Correct	1086 ms	174912 KB	Output is correct
17	Correct	959 ms	165496 KB	Output is correct
18	Correct	1253 ms	210552 KB	Output is correct
19	Correct	1401 ms	221304 KB	Output is correct
20	Correct	1146 ms	178040 KB	Output is correct
21	Correct	277 ms	77176 KB	Output is correct
22	Correct	275 ms	75384 KB	Output is correct
23	Correct	494 ms	117244 KB	Output is correct
24	Correct	773 ms	150904 KB	Output is correct
25	Correct	852 ms	111736 KB	Output is correct
26	Correct	722 ms	111736 KB	Output is correct
27	Correct	2518 ms	359032 KB	Output is correct
28	Correct	558 ms	95828 KB	Output is correct
29	Correct	76 ms	50680 KB	Output is correct
30	Correct	119 ms	55516 KB	Output is correct
31	Correct	2407 ms	330464 KB	Output is correct
32	Correct	2529 ms	336760 KB	Output is correct
33	Correct	2727 ms	336968 KB	Output is correct

Subtask #4
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	47328 KB	Output is correct
2	Correct	215 ms	47612 KB	Output is correct
3	Correct	130 ms	47480 KB	Output is correct
4	Correct	148 ms	47612 KB	Output is correct
5	Correct	231 ms	47720 KB	Output is correct
6	Correct	43 ms	47352 KB	Output is correct
7	Correct	46 ms	47352 KB	Output is correct
8	Correct	43 ms	47352 KB	Output is correct
9	Correct	44 ms	47352 KB	Output is correct
10	Correct	45 ms	47352 KB	Output is correct
11	Correct	209 ms	47568 KB	Output is correct
12	Correct	283 ms	47608 KB	Output is correct
13	Correct	477 ms	48012 KB	Output is correct
14	Correct	470 ms	47736 KB	Output is correct
15	Correct	45 ms	47224 KB	Output is correct
16	Correct	44 ms	47352 KB	Output is correct
17	Correct	47 ms	47224 KB	Output is correct
18	Execution timed out	3057 ms	117628 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	47328 KB	Output is correct
2	Correct	215 ms	47612 KB	Output is correct
3	Correct	130 ms	47480 KB	Output is correct
4	Correct	148 ms	47612 KB	Output is correct
5	Correct	231 ms	47720 KB	Output is correct
6	Correct	43 ms	47352 KB	Output is correct
7	Correct	46 ms	47352 KB	Output is correct
8	Correct	43 ms	47352 KB	Output is correct
9	Correct	44 ms	47352 KB	Output is correct
10	Correct	45 ms	47352 KB	Output is correct
11	Correct	209 ms	47568 KB	Output is correct
12	Correct	283 ms	47608 KB	Output is correct
13	Correct	477 ms	48012 KB	Output is correct
14	Correct	470 ms	47736 KB	Output is correct
15	Correct	45 ms	47224 KB	Output is correct
16	Correct	44 ms	47352 KB	Output is correct
17	Correct	47 ms	47224 KB	Output is correct
18	Execution timed out	3057 ms	117628 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

답안 #95794

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 0 / 12.0

Subtask #3 24.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
24.0 / 24.0

Subtask #4
0 / 27.0

Subtask #5
0 / 26.0