oj.uz

답안 #817864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817864 2023-08-09T18:18:14 Z Ozy 무지개나라 (APIO17_rainbow) C++17
0 / 100
 1 ms 468 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a <<  " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli> 

#define MAX 200000

lli dir[8] = {0,0,1,-1,-1,1,0,0};
lli vis[4][MAX+2];
lli acu[3][MAX+2],inval[3][MAX+2];
lli fil,col,res;

void dfs(pll pos,lli id) {

    queue<pll> cola;
    cola.push(pos);
    vis[pos.first][pos.second] = id;

    pll n_pos;
    while (!cola.empty()) {
        pos = cola.front();
        cola.pop();


        rep(i,0,3) {
            n_pos.first = pos.first + dir[i];
            n_pos.second = pos.second + dir[i+4];

            if(vis[n_pos.first][n_pos.second]) continue;

            vis[n_pos.first][n_pos.second] = id;
            cola.push(n_pos); 
        }

    }

}

//solucion subtask #2
void init(int R, int C, int sr, int sc, int M, char *S) {
    fil = R;
    col = C;
    rep(j,1,col) {
        vis[0][j] = 1;
        vis[4][j] = 1;
    }   
    vis[1][0] = 1;
    vis[1][col+1] = 1;
    vis[2][0] = 1;
    vis[2][col+1] = 1;

    pll pos = {sr,sc};
    rep(i,0,M-1) {
        vis[pos.first][pos.second] = 1;
        if (S[i] == 'N') pos.first--;
        if (S[i] == 'S') pos.first++;
        if (S[i] == 'W') pos.second--;
        if (S[i] == 'E') pos.second++;
    }
    vis[pos.first][pos.second] = 1;

    //hacer los acululados individuales
    rep(i,1,2) {
        rep(j,1,col) {
            acu[i][j] = acu[i][j-1];
            if (vis[i][j] == 1) {inval[i][j] = 1; continue;}
            if (vis[i][j-1] == 1) {
                inval[i][j] = 1;
                acu[i][j]++;
            }
        }   
    }

    //marcar los que son invalidos para el R = 2
    inval[0][0] = 1;
    rep(j,1,col) if(vis[1][j] && vis[2][j]) inval[0][j] = 1;

    //hacer los acumulados
    rep(j,1,col) {
        acu[0][j] = acu[0][j-1];
        if (vis[1][j] == 0) {
            inval[0][j] = 1;
            acu[0][j]++;
            dfs({1,j},acu[0][j]);
        } 
        if (vis[2][j] == 0) {
            inval[0][j] = 1;
            acu[0][j]++;
            dfs({2,j},acu[0][j]);
        } 
    }
}
//poner tambien que los inicios son invalidos

int colour(int ar, int ac, int br, int bc) {
    lli a;

    if (ar != bc) a = 0;
    else a = ar;

    lli res = acu[a][bc] - acu[a][ac-1];
    if (!inval[a][ac]) res++;
    return res;
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:50:14: warning: array subscript 4 is above array bounds of 'long long int [4][200002]' [-Warray-bounds]
   50 |         vis[4][j] = 1;
      |         ~~~~~^
rainbow.cpp:14:5: note: while referencing 'vis'
   14 | lli vis[4][MAX+2];
      |     ^~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 436 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -