oj.uz

Submission #54835

# Submission time Handle Problem Language Result Execution time Memory
54835 2018-07-05T08:04:54 Z top34051 Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 3000 ms 53164 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<8;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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Execution timed out 3010 ms 47652 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 47652 KB Output is correct
2 Correct 1312 ms 53032 KB Output is correct
3 Correct 1154 ms 53164 KB Output is correct
4 Correct 1224 ms 53164 KB Output is correct
5 Correct 578 ms 53164 KB Output is correct
6 Correct 68 ms 53164 KB Output is correct
7 Incorrect 139 ms 53164 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -