oj.uz

Submission #54821

# Submission time Handle Problem Language Result Execution time Memory
54821 2018-07-05T07:33:11 Z top34051 Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 473 ms 25076 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 = 1e5 + 5;

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

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

set<pii> ban, good;

set<pii> vis;

void dfs(int x, int y, int r1, int c1, int r2, int c2) {
    if(!(r1<=x && x<=r2 && c1<=y && y<=c2)) return ;
    vis.insert({x,y});
    for(int i=-1;i<=1;i++) {
        for(int j=-1;j<=1;j++) {
            pii t = {x+i, y+j};
            if(good.find(t)==good.end()) continue;
            if(vis.find(t)!=vis.end()) continue;
            dfs(x+i, y+j, 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<4;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) {
    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 33 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 436 KB Output is correct
2 Incorrect 2 ms 436 KB Output isn't correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 436 KB Output is correct
2 Correct 458 ms 25076 KB Output is correct
3 Correct 473 ms 25076 KB Output is correct
4 Correct 364 ms 25076 KB Output is correct
5 Correct 288 ms 25076 KB Output is correct
6 Incorrect 52 ms 25076 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 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 33 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -