oj.uz

Submission #54868

# Submission time Handle Problem Language Result Execution time Memory
54868 2018-07-05T08:29:11 Z top34051 Land of the Rainbow Gold (APIO17_rainbow) C++17
35 / 100
 3000 ms 158792 KB 
//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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -