제출 #107992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107992		oolimry	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	247 ms	263168 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;
typedef pair<long long, long long> ii;





int main()
{
    freopen("i.txt","r",stdin);
    long long n, m;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;

    ii doges[m];

    vector<long long> posDog[n];

    for(int i = 0;i < m;i++){
        cin >> doges[i].first >> doges[i].second;
        posDog[doges[i].first].push_back(i);
    }



    bool touched[n];
    fill(touched,touched+n,false);
    deque<ii> bfs;
    map<ii, long long> vis;

    bfs.push_back(doges[0]);
    vis[doges[0]] = 0ll;

    while(!bfs.empty()){
        ii u = bfs.front();
        bfs.pop_front();
        long long x = u.first;
        long long p = u.second;
        //cout << x << " " << p << " " << vis[u] << "\n";
		if(vis[u] < 0) return 1;
        if(x == doges[1].first){
            cout << vis[u];
            return 0;
        }

        if(!touched[x]){
            for(int i = 0;i < posDog[x].size();i++){
                ii v = doges[posDog[x][i]];
                if(vis.find(v) == vis.end()){
                    vis[v] = vis[u];
                    bfs.push_front(v);
                }
                else if(vis[v] > vis[u]){
                    vis[v] = vis[u];
                    bfs.push_front(v);
                }
            }
            touched[x] = true;
        }

        if(x - p >= 0){
            ii v = ii(x-p,p);
            if(vis.find(v) == vis.end()){
                vis[v] = vis[u] + 1;
                bfs.push_back(v);
            }
            else{
                if(vis[v] > vis[u] + 1){
                    vis[v] = vis[u] + 1;
                    bfs.push_back(v);
                }
            }
        }
        if(x + p < n){
            ii v = ii(x+p,p);
            if(vis.find(v) == vis.end()){
                vis[v] = vis[u] + 1;
                bfs.push_back(v);
            }
            else{
                if(vis[v] > vis[u] + 1){
                    vis[v] = vis[u] + 1;
                    bfs.push_back(v);
                }
            }
        }
    }

    cout << -1;
    return 0;

    //for(map<ii, long long>::iterator it = vis.begin();it != vis.end();it++){
    //    cout << it->first.first << " " << it->first.second << " " << it->second << "\n";
    //}








    return 0;
}

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

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:50:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0;i < posDog[x].size();i++){
                           ~~^~~~~~~~~~~~~~~~~~
skyscraper.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("i.txt","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~

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