oj.uz

Submission #54823

# Submission time Handle Problem Language Result Execution time Memory
54823 2018-07-05T07:35:55 Z top34051 Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 3000 ms 34448 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[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) {
    if(!(r1<=x && x<=r2 && c1<=y && y<=c2)) return ;
    vis.insert({x,y});
    for(int i=0;i<8;i++) {
        pii t = {x+cx[i], y+cy[i]};
        if(good.find(t)==good.end()) continue;
        if(vis.find(t)!=vis.end()) continue;
        dfs(x+cx[i], y+cy[i], 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) {
    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 37 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 3 ms 432 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Execution timed out 3046 ms 13596 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 13596 KB Output is correct
2 Correct 606 ms 25076 KB Output is correct
3 Correct 522 ms 25076 KB Output is correct
4 Correct 782 ms 34448 KB Output is correct
5 Correct 365 ms 34448 KB Output is correct
6 Incorrect 79 ms 34448 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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