제출 #1289397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289397		herominhsteve	Toy (CEOI24_toy)	C++20	100 / 100	400 ms	176900 KiB

Main

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "CEOI24_toy"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

int W,H,K,L;
int n,m;
vector<vector<int>> grid;

int hX,hY,vX,vY;
int tarX,tarY;

void init(){
    cin>>W>>H>>K>>L;
    cin>>hX>>hY>>vX>>vY;

    hX++; hY++; vX++; vY++;
    swap(hX,hY); swap(vX,vY);

    n = H, m = W;

    grid.assign(n+1,vector<int>(m+1,0));

    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            char x; 
            cin>>x;
            grid[i][j] = (x=='.');
            if (x=='*'){
                grid[i][j] = 1;
                tarX = i;
                tarY = j;
            }
        }
    }
}

inline int getID(int x,int y){
    return (x-1) * m + y;
}

inline bool isValid(int x,int y){
    return (x>=1 and x<=n and y>=1 and y<=m and grid[x][y]);
}

vector<vector<int>> rowL,rowR;
vector<vector<int>> colU,colD;

void comPre(){
    rowL.assign(n+1,vector<int>(m+1,0));
    rowR.assign(n+1,vector<int>(m+2,0));
    colU.assign(n+1,vector<int>(m+1,0));
    colD.assign(n+2,vector<int>(m+1,0));

    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++)
            rowL[i][j] = (grid[i][j] ? rowL[i][j-1] + 1 : 0);
        for (int j=m;j>=1;j--)
            rowR[i][j] = (grid[i][j] ? rowR[i][j+1] + 1 : 0);
    }

    for (int j=1;j<=m;j++){
        for (int i=1;i<=n;i++)
            colU[i][j] = (grid[i][j] ? colU[i-1][j] + 1 : 0);
        for (int i=n;i>=1;i--)
            colD[i][j] = (grid[i][j] ? colD[i+1][j] + 1 : 0);
    }
}

// R D L U
const int dx[] = {+0,+1,+0,-1};
const int dy[] = {+1,+0,-1,+0};

vector<vector<int>> graph;

void buildGraph(){
    graph.resize(n * m + 1);
    for (int x = 1; x <= n ; x++){
        for (int y = 1; y <= m ; y++){
            if (!grid[x][y]) continue;
            int curID = getID(x,y);
            if (rowL[x][y] + rowR[x][y] - 1 >= K){
                for (int dir : {0,2}){
                    int newx = x + dx[dir];
                    int newy = y + dy[dir];
                    if (isValid(newx,newy)){
                        int U = min(colU[x][y],colU[newx][newy]);
                        int D = min(colD[x][y],colD[newx][newy]);
                        if (U + D - 1 >= L){
                            graph[curID].push_back(getID(newx,newy));
                        }
                    }
                }
            }
            if (colU[x][y] + colD[x][y] - 1 >= L){
                for (int dir : {1,3}){
                    int newx = x + dx[dir];
                    int newy = y + dy[dir];
                    if (isValid(newx,newy)){
                        int Le = min(rowL[x][y],rowL[newx][newy]);
                        int Ri = min(rowR[x][y],rowR[newx][newy]);
                        if (Le + Ri - 1 >= K){
                            graph[curID].push_back(getID(newx,newy));
                        }
                    }
                }
            }
        }
    }
}

void sol(){
	comPre();
    buildGraph();

    vector<int> visited(n * m + 1 , 0);
    queue<int> qu;
    visited[getID(hX,vY)] = 1;
    qu.push(getID(hX,vY));

    while (!qu.empty()){
        int u = qu.front(); qu.pop();
        for (int v : graph[u]){
            if (visited[v]) continue;
            visited[v] = 1;
            qu.push(v);
        }
    }

    cout<<(visited[getID(tarX,tarY)] ? "YES" : "NO");
}

int main(){
    setup();
    init();
    sol();
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void setup()':
Main.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27