oj.uz

답안 #1028393

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1028393 2024-07-19T19:02:29 Z _8_8_ 무지개나라 (APIO17_rainbow) C++17
0 / 100
 3000 ms 90820 KB 
#include <bits/stdc++.h>
#include "rainbow.h"
 
using namespace std;
 
vector<pair<int,int>> pts;
void init(int R, int C, int sr, int sc, int M, char *S) {
    pts.push_back({sr,sc});
    for(int i = 0;i < M;i++){
        if(S[i] == 'N'){
            sr--;
        }else if(S[i] == 'S'){
            sr++;
        }else if(S[i] == 'W'){
            sc--;
        }else{
            sc++;
        }
        assert(sr <= R && sr >= 1);
        assert(sc <= C && sc >= 1);
        pts.push_back({sr,sc});
    }
    sort(pts.begin(),pts.end());
    pts.resize(unique(pts.begin(),pts.end()) - pts.begin());
}
map<pair<int,int>,bool> k,vis;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
int colour(int ar, int ac, int br, int bc) {
    // V - E + F = 1 + C -> F = 1 + C - V + E
    k.clear();
    vis.clear();
    int V = 0,E = 0,C = 0;
    for(auto [r,c]:pts){
        if(r >= ar && r <= br && c >= ac && c <= bc){
            k[{r,c}] = 1;
        }
    }
    for(int i = ar - 1;i <= br + 1;i++){
        k[{i,ac-1}] = k[{i,bc+1}] = 1;
    }
    for(int i = ac - 1;i <= bc + 1;i++){
        k[{ar-1,i}] = k[{br+1,i}] = 1;
    }
    int bf = 0;
    for(auto [xx,_y]:k){
        auto [r,c] = xx;
        if(k.count({r + 1,c}) && k.count({r,c + 1}) && k.count({r + 1,c + 1})){
            bf++;
        }
        if(k.count({r+1,c+1}) && !k.count({r+1,c}) && !k.count({r,c+1})){
            E += 2;
        }
        if(k.count({r+1,c-1}) && !k.count({r+1,c}) && !k.count({r,c-1})){
            E += 2;
        }
        if(!vis.count({r,c})){
            C++;
            queue<pair<int,int>> q;
            q.push({r,c});
            vis[{r,c}]=1;
            while(!q.empty()){
                V++;
                auto [x,y] = q.front();q.pop();
                // cout << x << ' ' << y << '\n';
                for(int i = 0;i < 4;i++){
                    int _x = x + dx[i],_y = y + dy[i];
                    if(k.count({_x,_y})){
                        E++;
                    }
                    if(k.count({_x,_y}) && !vis.count({_x,_y})){
                        vis[{_x,_y}]=1;
                        q.push({_x,_y});
                    }
                }
            }
        }
    }
  	C=1;
    assert(E%2==0);
    E /= 2;     
    // cout << V << ' ' << C << ' ' << E << '\n';
    return C - V + E - bf;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 344 KB Output is correct
2 Correct 128 ms 348 KB Output is correct
3 Incorrect 80 ms 596 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

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

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 573 ms 45044 KB Output is correct
3 Correct 533 ms 45140 KB Output is correct
4 Correct 508 ms 38852 KB Output is correct
5 Correct 232 ms 21444 KB Output is correct
6 Correct 873 ms 63240 KB Output is correct
7 Incorrect 1369 ms 90820 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 344 KB Output is correct
2 Correct 128 ms 348 KB Output is correct
3 Incorrect 80 ms 596 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 344 KB Output is correct
2 Correct 128 ms 348 KB Output is correct
3 Incorrect 80 ms 596 KB Output isn't correct
4 Halted 0 ms 0 KB -