답안 #54868 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54868	2018-07-05T08:29:11 Z	top34051	무지개나라 (APIO17_rainbow)	C++17	35 / 100	3000 ms	158792 KB

rainbow

//Subtask 3

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

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 2e5 + 5;

int n,m,k;
pii a[maxn];

int cx[10] = {0,0,1,-1,-1,-1,1,1};
int cy[10] = {1,-1,0,0,-1,1,-1,1};

set<pii> ban, good;

set<pii> vis;

void dfs(int x, int y, int r1, int c1, int r2, int c2) {
//    printf("%d %d\n",x,y);
    vis.insert({x,y});
    for(int i=0;i<4;i++) {
        pii t = {x+cx[i], y+cy[i]};
        if(!(r1<=t.X && t.X<=r2 && c1<=t.Y && t.Y<=c2)) continue;
        if(vis.find(t)!=vis.end()) continue;
        int ok = 0;
        if((t.X==r1 || t.X==r2 || t.Y==c1 || t.Y == c2) && ban.find(t)==ban.end()) ok = 1;
        else if(good.find(t)!=good.end()) ok = 1;
        if(ok) dfs(t.X, t.Y, r1,c1,r2,c2);
    }
}

void init(int R, int C, int sr, int sc, int M, char *s) {
	n = R; m = C; k = M;
	a[1] = {sr, sc};
	for(int i=0;i<k;i++) {
        a[i+2] = a[i+1];
		if(s[i]=='N') a[i+2].X--;
		if(s[i]=='E') a[i+2].Y++;
		if(s[i]=='W') a[i+2].Y--;
		if(s[i]=='S') a[i+2].X++;
	}
	k++;
	for(int i=1;i<=k;i++) {
        ban.insert({a[i].X,a[i].Y});
//        printf("ban %d %d\n",a[i].X,a[i].Y);
	}

    for(int i=1;i<=k;i++) {
        for(int j=0;j<8;j++) {
            pii t = {a[i].X + cx[j], a[i].Y + cy[j]};
            if(ban.find(t)!=ban.end()) continue;
            if(good.find(t)!=good.end()) continue;
            good.insert(t);
//            printf("good %d %d\n",t.X,t.Y);
        }
    }
}

int colour(int ar, int ac, int br, int bc) {
    //isolate
    int cnt = 0;
    for(auto t : ban) {
        if(ar<=t.X && t.X<=br && ac<=t.Y && t.Y<=bc) cnt++;
    }
    if(cnt==0) return 1;
    //general
    int res = 0;
    vis.clear();
    for(auto t : good) {
        if(!(ar<=t.X && t.X<=br && ac<=t.Y && t.Y<=bc)) continue;
        if(vis.find(t)!=vis.end()) continue;
        dfs(t.X,t.Y,ar,ac,br,bc);
        res++;
    }
    return res;
}

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	376 KB	Output is correct
2	Correct	137 ms	716 KB	Output is correct
3	Correct	46 ms	716 KB	Output is correct
4	Correct	66 ms	716 KB	Output is correct
5	Correct	133 ms	772 KB	Output is correct
6	Correct	3 ms	772 KB	Output is correct
7	Correct	3 ms	772 KB	Output is correct
8	Correct	2 ms	772 KB	Output is correct
9	Correct	3 ms	980 KB	Output is correct
10	Correct	3 ms	980 KB	Output is correct
11	Correct	93 ms	1224 KB	Output is correct
12	Correct	99 ms	1224 KB	Output is correct
13	Correct	238 ms	1356 KB	Output is correct
14	Correct	133 ms	1356 KB	Output is correct
15	Correct	3 ms	1356 KB	Output is correct
16	Correct	3 ms	1356 KB	Output is correct
17	Correct	2 ms	1356 KB	Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1356 KB	Output is correct
2	Correct	939 ms	53596 KB	Output is correct
3	Correct	858 ms	53596 KB	Output is correct
4	Correct	1051 ms	53596 KB	Output is correct
5	Correct	469 ms	53596 KB	Output is correct
6	Correct	87 ms	53596 KB	Output is correct
7	Correct	128 ms	53596 KB	Output is correct
8	Correct	229 ms	53596 KB	Output is correct
9	Correct	227 ms	53596 KB	Output is correct
10	Correct	92 ms	53596 KB	Output is correct
11	Correct	203 ms	53596 KB	Output is correct
12	Correct	395 ms	53596 KB	Output is correct
13	Correct	325 ms	53596 KB	Output is correct
14	Correct	268 ms	53596 KB	Output is correct
15	Correct	241 ms	53596 KB	Output is correct
16	Correct	66 ms	53596 KB	Output is correct
17	Correct	114 ms	53596 KB	Output is correct
18	Correct	229 ms	53596 KB	Output is correct
19	Correct	1107 ms	92344 KB	Output is correct
20	Correct	975 ms	92344 KB	Output is correct
21	Correct	322 ms	92344 KB	Output is correct
22	Correct	331 ms	92344 KB	Output is correct
23	Correct	309 ms	92344 KB	Output is correct
24	Correct	608 ms	92344 KB	Output is correct
25	Correct	692 ms	92344 KB	Output is correct
26	Correct	654 ms	92344 KB	Output is correct
27	Correct	1937 ms	158792 KB	Output is correct
28	Correct	486 ms	158792 KB	Output is correct
29	Correct	71 ms	158792 KB	Output is correct
30	Correct	111 ms	158792 KB	Output is correct
31	Correct	1222 ms	158792 KB	Output is correct
32	Correct	1687 ms	158792 KB	Output is correct
33	Correct	1638 ms	158792 KB	Output is correct

Subtask #4
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	376 KB	Output is correct
2	Correct	137 ms	716 KB	Output is correct
3	Correct	46 ms	716 KB	Output is correct
4	Correct	66 ms	716 KB	Output is correct
5	Correct	133 ms	772 KB	Output is correct
6	Correct	3 ms	772 KB	Output is correct
7	Correct	3 ms	772 KB	Output is correct
8	Correct	2 ms	772 KB	Output is correct
9	Correct	3 ms	980 KB	Output is correct
10	Correct	3 ms	980 KB	Output is correct
11	Correct	93 ms	1224 KB	Output is correct
12	Correct	99 ms	1224 KB	Output is correct
13	Correct	238 ms	1356 KB	Output is correct
14	Correct	133 ms	1356 KB	Output is correct
15	Correct	3 ms	1356 KB	Output is correct
16	Correct	3 ms	1356 KB	Output is correct
17	Correct	2 ms	1356 KB	Output is correct
18	Execution timed out	3023 ms	158792 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	376 KB	Output is correct
2	Correct	137 ms	716 KB	Output is correct
3	Correct	46 ms	716 KB	Output is correct
4	Correct	66 ms	716 KB	Output is correct
5	Correct	133 ms	772 KB	Output is correct
6	Correct	3 ms	772 KB	Output is correct
7	Correct	3 ms	772 KB	Output is correct
8	Correct	2 ms	772 KB	Output is correct
9	Correct	3 ms	980 KB	Output is correct
10	Correct	3 ms	980 KB	Output is correct
11	Correct	93 ms	1224 KB	Output is correct
12	Correct	99 ms	1224 KB	Output is correct
13	Correct	238 ms	1356 KB	Output is correct
14	Correct	133 ms	1356 KB	Output is correct
15	Correct	3 ms	1356 KB	Output is correct
16	Correct	3 ms	1356 KB	Output is correct
17	Correct	2 ms	1356 KB	Output is correct
18	Execution timed out	3023 ms	158792 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

답안 #54868

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