oj.uz

Submission #1050526

# Submission time Handle Problem Language Result Execution time Memory
1050526 2024-08-09T10:30:05 Z vjudge1 Sky Walking (IOI19_walk) C++17
0 / 100
 2630 ms 1048576 KB 
#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});
}

Compilation message

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:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int j=0; j<bpoi[i].size()-1; j++){
      |                      ~^~~~~~~~~~~~~~~~~
walk.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int j=0; j<spoi[i].size()-1; j++){
      |                      ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 984 ms 218132 KB Output is correct
4 Incorrect 1106 ms 261576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 29772 KB Output is correct
2 Runtime error 2630 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 29772 KB Output is correct
2 Runtime error 2630 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -