제출 #679855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679855		79brue	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	249 ms	94812 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int G = 175;

struct dat{
    int x, doge, dist;
    dat(){}
    dat(int x, int doge, int dist): x(x), doge(doge), dist(dist){}
};

int n, k;
bool visited1[30002][180];
bool visited2[30002][180];
bool started[30002];
int st[30002], a[30002], b[30002], idx[30002];
vector<int> lst[30002];

dat que[10000002];
int que_size, que_front;

dat pop(){
    return que[que_front++];
}

void push(dat tmp){
    que[que_size++] = tmp;
}

inline bool chk(int d, int x){
    if(b[d] <= G) return visited1[x][b[d]];
    return visited2[idx[d]][x/b[d]];
}

inline void mark(int d, int x){
    if(b[d] <= G) visited1[x][b[d]] = 1;
    else visited2[idx[d]][x/b[d]] = 1;
}

inline void go(dat &tmp){
    int r = b[tmp.doge];
    if(tmp.x - r >= 0 && !chk(tmp.doge, tmp.x - r)) mark(tmp.doge, tmp.x-r), push(dat(tmp.x - r, tmp.doge, tmp.dist+1));
    if(tmp.x + r <  n && !chk(tmp.doge, tmp.x + r)) mark(tmp.doge, tmp.x+r), push(dat(tmp.x + r, tmp.doge, tmp.dist+1));
}

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=k; i++){
        scanf("%d %d", &st[i], &b[i]);
        a[i] = st[i] % b[i];
        lst[st[i]].push_back(i);
    }

    vector<pair<int, int> > vec;
    for(int i=1; i<=k; i++) vec.push_back(make_pair(a[i], b[i]));
    sort(vec.begin(), vec.end());
    for(int i=1; i<=k; i++){
        int tmp = lower_bound(vec.begin(), vec.end(), make_pair(a[i], b[i])) - vec.begin() + 1;
        idx[i] = tmp;
    }

    push(dat(st[1], 1, 0));
    mark(1, st[1]);
    while(que_size != que_front){
        dat tmp = pop();
//        printf("x: %d, doge: %d, dist: %d\n", tmp.x, tmp.doge, tmp.dist);
        if(tmp.doge == 2){
            printf("%d", tmp.dist);
            return 0;
        }
        if(!started[tmp.x]){
            started[tmp.x] = 1;
            for(int d: lst[tmp.x]){
                if(d == 2){
                    printf("%d", tmp.dist);
                    return 0;
                }
                if(chk(d, tmp.x)) continue;
                mark(d, tmp.x);
                dat tmp2 = dat(tmp.x, d, tmp.dist);
                go(tmp2);
            }
        }
        go(tmp);
    }

    printf("-1");
}

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

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d %d", &st[i], &b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43