oj.uz

Submission #1096662

# Submission time Handle Problem Language Result Execution time Memory
1096662 2024-10-05T00:10:37 Z azberjibiou Sky Walking (IOI19_walk) C++17
33 / 100
 779 ms 103304 KB 
#include "walk.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=100050;
const int mxM=10000;
const int mxK=60;
const ll INF=1e18;
struct line{
    int l, r, h;
};
int N, M;
int pos[mxN], A[mxN];
line B[mxN];
int st, en;
int sidx, eidx;
map <pii, int> vtx;
pii V[12*mxN];
int vidx;
vector <pll> adj[12*mxN];
/*
void input(){
    cin >> N >> M;
    for(int i=0;i<N;i++) cin >> pos[i];
    for(int i=0;i<N;i++) cin >> A[i];
    for(int i=1;i<=M;i++) cin >> B[i].l >> B[i].r >> B[i].h;
    for(int i=1;i<=M;i++) B[i].l=pos[B[i].l], B[i].r=pos[B[i].r];
    cin >> st >> en;
}
*/
void no_endpoint(){
    vector <line> v;
    for(int i=1;i<=M;i++) v.push_back(B[i]);
    sort(all(v), [](line a, line b){return a.h!=b.h ? a.h<b.h : a.l<b.l;});
    vector <line> res;
    line prev={-1, -1, -1};
    for(line x : v){
        if(x.h!=prev.h || prev.r<x.l){
            if(prev.h!=-1) res.push_back(prev);
            prev=x;
        }
        else prev.r=x.r;
    }
    if(prev.h!=-1) res.push_back(prev);
    M=res.size();
    for(int i=1;i<=M;i++) B[i]=res[i-1];
}
void init(vector <int> x, vector <int> h, vector <int> l, vector <int> r, vector <int> y, int s, int g){
    N=x.size(); M=l.size();
    for(int i=0;i<N;i++) pos[i]=x[i];
    for(int i=0;i<N;i++) A[i]=h[i];
    for(int i=1;i<=M;i++) B[i].l=l[i-1], B[i].r=r[i-1], B[i].h=y[i-1];
  	for(int i=1;i<=M;i++) B[i].l=pos[B[i].l], B[i].r=pos[B[i].r];
    no_endpoint();
    st=s, en=g;
}
void add_edge(int a, int b, int c){
    adj[a].emplace_back(b, c);
    adj[b].emplace_back(a, c);
}
void add(vector <int> &v1, int val, pii rng){
    if(val==-1) return;
    if(val>rng.se || val<rng.fi) return;
    v1.push_back(val);
}
int lb(set <int> &s, int val){
    auto it=s.lower_bound(val);
    return (it==s.end() ? -1 : *it);
}
int rb(set <int> &s, int val){
    auto it=s.lower_bound(val+1);
    if(it==s.begin()) return -1;
    it--;
    return *it;
}
void make_graph(){
    set <int> xcr;
    set <pii> fall; // x값, 끝점 index
    vector <pii> hv;
    for(int i=0;i<N;i++) hv.emplace_back(A[i], i);
    sort(all(hv));
    vector <int> turn;
    for(int i=1;i<=M;i++) turn.push_back(i);
    sort(all(turn), [&](int a, int b){return B[a].h>B[b].h;});
    for(int now : turn){
        auto [nl, nr, nh]=B[now];
        while(hv.size() && hv.back().fi>=nh){
            int idx=hv.back().se;
            hv.pop_back();
            xcr.insert(pos[idx]);
        }
        vector <int> cr;
        vector <pii> up; // x값, 끝점 index
        vector <int> down;
        //get up edges
        while(true){
            if(fall.empty()) break;
            auto it=fall.lower_bound(pii(nl, 0));
            if(it==fall.end() || it->fi>nr) break;
            up.push_back(*it);
            fall.erase(it);
        }
        // add down vertices
        add(down, lb(xcr, nl), pii(nl, nr));
        if(A[st]>=nh && nl<=pos[st] && pos[st]<=nr){
            add(down, lb(xcr, pos[st]), pii(nl, nr));
            add(down, rb(xcr, pos[st]), pii(nl, nr));
        }
        if(A[en]>=nh && nl<=pos[en] && pos[en]<=nr){
            add(down, lb(xcr, pos[en]), pii(nl, nr));
            add(down, rb(xcr, pos[en]), pii(nl, nr));
        }
        add(down, rb(xcr, nr), pii(nl, nr));
        sort(all(down));
        down.erase(unique(all(down)), down.end());
        /*
        printf("nl, nr, nh=%d %d %d\n", nl, nr, nh);
        for(int x : down) printf("%d ", x);
        printf("\n");
        printf("xcr: ");
        for(int x : xcr) printf("%d ", x);
        printf("\n");
        */
        //make vertices
        for(int x : down) cr.push_back(x);
        for(auto [x, idx] : up) cr.push_back(x);
        sort(all(cr));
        cr.erase(unique(all(cr)), cr.end());
        for(int i=0;i<cr.size();i++){
            int x=cr[i];
            if(vtx.count(pii(x, nh))==0){
              	V[vidx]=pii(x, nh);
            	vtx[pii(x, nh)]=vidx++;
            }
            //also make horizontal edges
            if(i-1>=0) add_edge(vtx[pii(x, nh)], vtx[pii(cr[i-1], nh)], cr[i]-cr[i-1]);
        }
        //make up edges
        for(auto [x, num1] : up){
            int num2=vtx[pii(x, nh)];
            add_edge(num1, num2, V[num1].se-nh);
        }
        //make down edges
        for(int x : down){
            fall.insert(pii(x, vtx[pii(x, nh)]));
        }
    }
    //make st and en
    V[vidx]=pii(pos[st], 0);
    vtx[pii(pos[st], 0)]=vidx;
    sidx=vidx++;
    V[vidx]=pii(pos[en], 0);
    vtx[pii(pos[en], 0)]=vidx;
    eidx=vidx++;
    //adding edge for st and en
    auto itst=fall.lower_bound(pii(pos[st], 0));
    if(itst!=fall.end() && itst->fi==pos[st]){
        int nxt=itst->se;
        add_edge(sidx, nxt, V[nxt].se);
    }
    auto iten=fall.lower_bound(pii(pos[en], 0));
    if(iten!=fall.end() && iten->fi==pos[en]){
        int nxt=iten->se;
        add_edge(eidx, nxt, V[nxt].se);
    }
    /*
    for(int i=0;i<vidx;i++) printf("V[%d]=%d %d\n", i, V[i].fi, V[i].se);
    for(int i=0;i<vidx;i++){
        printf("i=%d: ", i);
        for(auto [x, y] : adj[i]) printf("(%lld %lld) ", x, y);
        printf("\n");
    }
    */
}
ll dist[12*mxN];
ll ans;
void dijkstra(){
    for(int i=0;i<vidx;i++) dist[i]=-1;
    priority_queue <pll> pq;
    pq.emplace(0, sidx);
    while(pq.size()){
        auto [x, now]=pq.top();
        pq.pop();
        if(dist[now]!=-1) continue;
        dist[now]=-x;
        for(auto [nxt, val] : adj[now]) pq.emplace(x-val, nxt);
    }
    //for(int i=0;i<vidx;i++) printf("dist[%d]=%lld\n", i, dist[i]);
    ans=dist[eidx];
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	init(x, h, l, r, y, s, g);
    make_graph();
    dijkstra();
    return ans;
}
/*
int main(){
    gibon
    input();
    make_graph();
    dijkstra();
    cout << ans;
}
*/
/*
7 7
0 3 5 7 10 12 14
8 7 9 7 6 6 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5
*/

Compilation message

walk.cpp: In function 'void make_graph()':
walk.cpp:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         for(int i=0;i<cr.size();i++){
      |                     ~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28508 KB Output is correct
2 Correct 12 ms 28504 KB Output is correct
3 Correct 10 ms 28464 KB Output is correct
4 Correct 12 ms 28504 KB Output is correct
5 Correct 11 ms 28504 KB Output is correct
6 Correct 10 ms 28508 KB Output is correct
7 Correct 10 ms 28508 KB Output is correct
8 Correct 12 ms 28508 KB Output is correct
9 Correct 11 ms 28508 KB Output is correct
10 Correct 12 ms 28648 KB Output is correct
11 Correct 12 ms 28504 KB Output is correct
12 Correct 12 ms 28508 KB Output is correct
13 Correct 11 ms 28508 KB Output is correct
14 Incorrect 10 ms 28508 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 28504 KB Output is correct
2 Correct 10 ms 28552 KB Output is correct
3 Correct 600 ms 80876 KB Output is correct
4 Correct 673 ms 88748 KB Output is correct
5 Correct 409 ms 75268 KB Output is correct
6 Correct 373 ms 73260 KB Output is correct
7 Correct 380 ms 75440 KB Output is correct
8 Correct 605 ms 83088 KB Output is correct
9 Correct 526 ms 84488 KB Output is correct
10 Incorrect 643 ms 89116 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 32088 KB Output is correct
2 Correct 609 ms 87848 KB Output is correct
3 Correct 677 ms 89472 KB Output is correct
4 Correct 779 ms 96620 KB Output is correct
5 Correct 727 ms 96932 KB Output is correct
6 Correct 696 ms 93928 KB Output is correct
7 Correct 335 ms 66856 KB Output is correct
8 Correct 399 ms 71404 KB Output is correct
9 Correct 639 ms 90736 KB Output is correct
10 Correct 255 ms 72560 KB Output is correct
11 Correct 26 ms 32460 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 32088 KB Output is correct
2 Correct 609 ms 87848 KB Output is correct
3 Correct 677 ms 89472 KB Output is correct
4 Correct 779 ms 96620 KB Output is correct
5 Correct 727 ms 96932 KB Output is correct
6 Correct 696 ms 93928 KB Output is correct
7 Correct 335 ms 66856 KB Output is correct
8 Correct 399 ms 71404 KB Output is correct
9 Correct 639 ms 90736 KB Output is correct
10 Correct 255 ms 72560 KB Output is correct
11 Correct 26 ms 32460 KB Output is correct
12 Correct 683 ms 89476 KB Output is correct
13 Correct 601 ms 96628 KB Output is correct
14 Correct 735 ms 103304 KB Output is correct
15 Correct 439 ms 92268 KB Output is correct
16 Correct 524 ms 95344 KB Output is correct
17 Correct 605 ms 103020 KB Output is correct
18 Correct 457 ms 92272 KB Output is correct
19 Correct 530 ms 94476 KB Output is correct
20 Correct 393 ms 68336 KB Output is correct
21 Correct 73 ms 38720 KB Output is correct
22 Correct 490 ms 88660 KB Output is correct
23 Correct 459 ms 87100 KB Output is correct
24 Correct 373 ms 76528 KB Output is correct
25 Correct 430 ms 83372 KB Output is correct
26 Correct 327 ms 71688 KB Output is correct
27 Correct 769 ms 102308 KB Output is correct
28 Correct 660 ms 100524 KB Output is correct
29 Correct 730 ms 99908 KB Output is correct
30 Correct 368 ms 69920 KB Output is correct
31 Correct 668 ms 96656 KB Output is correct
32 Correct 249 ms 73948 KB Output is correct
33 Correct 263 ms 76148 KB Output is correct
34 Correct 301 ms 77948 KB Output is correct
35 Correct 310 ms 80448 KB Output is correct
36 Correct 320 ms 75868 KB Output is correct
37 Correct 230 ms 73004 KB Output is correct
38 Correct 240 ms 76404 KB Output is correct
39 Correct 366 ms 81044 KB Output is correct
40 Correct 248 ms 75428 KB Output is correct
41 Correct 283 ms 73000 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28508 KB Output is correct
2 Correct 12 ms 28504 KB Output is correct
3 Correct 10 ms 28464 KB Output is correct
4 Correct 12 ms 28504 KB Output is correct
5 Correct 11 ms 28504 KB Output is correct
6 Correct 10 ms 28508 KB Output is correct
7 Correct 10 ms 28508 KB Output is correct
8 Correct 12 ms 28508 KB Output is correct
9 Correct 11 ms 28508 KB Output is correct
10 Correct 12 ms 28648 KB Output is correct
11 Correct 12 ms 28504 KB Output is correct
12 Correct 12 ms 28508 KB Output is correct
13 Correct 11 ms 28508 KB Output is correct
14 Incorrect 10 ms 28508 KB Output isn't correct
15 Halted 0 ms 0 KB -