제출 #1050483

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1050483		vjudge1	Sky Walking (IOI19_walk)	C++17	0 / 100	2577 ms	1048576 KiB

walk

#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
//#define int long long
#define ii pair<long long,int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define mid (l+r)/2
#define inf 1e15
#define MOD 1000000007
#define MX 100005
using namespace std;

map<ii, vii> edges;
map<ii, int> dist;
int dijkstra(ii s, ii t){
    priority_queue<pair<int, ii>, vector<pair<int, ii>>, greater<pair<int, ii>>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while(pq.size()){
        auto u = pq.top(); pq.pop();
        if(u.nd==t) break;
        if(u.st > dist[u.nd]) continue;
        for(auto p:edges[u.nd]){
            if(dist[p] > u.st + abs(u.nd.st-p.st) + abs(u.nd.nd-p.nd)){
                dist[p] = u.st + abs(u.nd.st-p.st) + abs(u.nd.nd-p.nd);
                pq.push({dist[p], p});
            }
        }
    }
    return dist[t];
}

int64_t min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t s, int32_t g){
    int bn = x.size(), sn = l.size();
    set<int> temp;
    vi yind={0};
    for(int i=0; i<bn; i++) temp.insert(h[i]);
    for(int i=0; i<sn; i++) temp.insert(y[i]);
    map<int, int> inv;
    for(auto i:temp){
        inv[i] = yind.size();
        yind.pb(i);
    }

    map<int, vi> lef, rig;
    for(int i=0; i<sn; i++){
        lef[l[i]].pb(i);
        rig[r[i]].pb(i);
    }
    
    vi bpoi[bn], spoi[sn];
    set<ii> cur;
    for(int i=0; i<bn; i++){
        bpoi[i].pb(0);
        dist[{x[i], 0}] = INT_MAX;
        //open
        for(auto j:lef[i]){
            //cerr << "opening" spc y[j] << endl;
            cur.insert({y[j],j});
        }
        //count
        for(auto j:cur){
            if(j.st>h[i]) break;
            bpoi[i].pb(j.st);
            spoi[j.nd].pb(x[i]);
            dist[{x[i], j.st}]=INT_MAX;
        }
        for(int j=0; j<bpoi[i].size()-1; j++){
            edges[{x[i], bpoi[i][j]}].pb({x[i], bpoi[i][j+1]});
            edges[{x[i], bpoi[i][j+1]}].pb({x[i], bpoi[i][j]});
            //cerr << x[i] spc bpoi[i][j] spc "to" spc x[i] spc bpoi[i][j+1] << endl;
        }
        //close
        for(auto j:rig[i]){
            //cerr << "closing" spc y[j] << endl;
            cur.erase({y[j],j});
        }
    }
    for(int i=0; i<sn; i++){
        for(int j=0; j<spoi[i].size()-1; j++){
            edges[{spoi[i][j], y[i]}].pb({spoi[i][j+1], y[i]});
            edges[{spoi[i][j+1], y[i]}].pb({spoi[i][j], y[i]});
            //cerr << spoi[i][j] spc y[i] spc "to" spc spoi[i][j+1] spc y[i] << endl;
        }
    }
    return dijkstra({x[s], 0}, {x[g], 0});
}

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

walk.cpp: In function 'int64_t min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int32_t, int32_t)':
walk.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int j=0; j<bpoi[i].size()-1; j++){
      |                      ~^~~~~~~~~~~~~~~~~
walk.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int j=0; j<spoi[i].size()-1; j++){
      |                      ~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43