oj.uz

Submission #1047080

# Submission time Handle Problem Language Result Execution time Memory
1047080 2024-08-07T08:40:46 Z vjudge1 Sky Walking (IOI19_walk) C++17
33 / 100
 2073 ms 1048576 KB 
#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
map<int,int>pos[100100];
vector<pair<int,int>> adj[1<<20];
int CC;
void AE(int a,int b,int c){
    adj[a].push_back({b,c});
    adj[b].push_back({a,c});
}
int whatpos(int i,int j){
    if(pos[i].count(j))
        return pos[i][j];
    pos[i][j]=++CC;
    auto it=pos[i].find(j);
    if(it!=pos[i].begin())
        AE(prev(it)->second,CC,it->first-prev(it)->first);
    if(next(it)!=pos[i].end())
        AE(next(it)->second,CC,next(it)->first-it->first);
    return CC;
}
long long dis[1<<20];
long long djik(int a,int b){
    memset(dis,9,sizeof dis);
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>> pq;
    pq.push({0,a});
    dis[a]=0;
    while(pq.size()){
        auto[d,x]=pq.top();
        pq.pop();
        if(d-dis[x])continue;
        for(auto[v,w]:adj[x])
            if(dis[v]>d+w)
                pq.push({dis[v]=d+w,v});
    }
    return dis[b]<dis[0]?dis[b]:-1;
}
set<int>intersection[100100];
map<int,int>lft,rt;
void makestuf(vector<int>h,int pos){
    lft.clear();
    rt.clear();
    int n=h.size();
    for(int i=0;i<=pos;i++)
        lft[h[i]]=max(lft[h[i]],i);
    for(int i=pos;i<n;i++)
        if(rt.count(h[i]))
            rt[h[i]]=min(rt[h[i]],i);
        else rt[h[i]]=i;
    auto it=lft.end();
    while(--it!=lft.begin())
        if(it->second>=prev(it)->second)
            it=lft.erase(prev(it));
    it=rt.end();
    while(--it!=rt.begin())
        if(it->second<=prev(it)->second)
            it=rt.erase(prev(it));
}
long long min_distance(VI x,VI h,VI l,VI r,VI y,int s,int g) {
    int m=l.size();
    makestuf(h,s);
    for(int i=0;i<m;i++)
        if(l[i]<s&&r[i]>s) {
            int A=lft.lower_bound(y[i])->second;
            int B=rt.lower_bound(y[i])->second;
            if(A-l[i])
                l.push_back(l[i]),
                r.push_back(l[i]=A),
                y.push_back(y[i]);
            if(B-r[i])
                r.push_back(r[i]),
                l.push_back(r[i]=B),
                y.push_back(y[i]);
        }
    m=l.size();
    makestuf(h,g);
    for(int i=0;i<m;i++)
        if(l[i]<g&&r[i]>g) {
            int A=lft.lower_bound(y[i])->second;
            int B=rt.lower_bound(y[i])->second;
            if(A-l[i])
                l.push_back(l[i]),
                r.push_back(l[i]=A),
                y.push_back(y[i]);
            if(B-r[i])
                r.push_back(r[i]),
                l.push_back(r[i]=B),
                y.push_back(y[i]);
        }
    m=l.size();
    vector<pair<int,int>> endpts;
    for(int i=0;i<m;i++) if(l[i]-r[i])
        endpts.push_back({l[i],i}),
        endpts.push_back({r[i],i}),
        whatpos(l[i],y[i]),whatpos(r[i],y[i]);
    sort(endpts.begin(),endpts.end());
    set<pair<int,int>> active;
    for(auto[b,i]:endpts){
        int pos=y[i];
        if(active.lower_bound({pos,0})!=active.begin()){
            auto it=--active.lower_bound({pos,0});
            intersection[it->second].insert(b);
            whatpos(b,it->first);
        }
        if(active.count({pos,i}))
            active.erase({pos,i});
        else active.insert({pos,i});
    }
    for(int i=0;i<m;i++){
        if(l[i]==r[i])continue;
        intersection[i].erase(l[i]);
        intersection[i].insert(r[i]);
        int prvind=whatpos(l[i],y[i]),prvpos=x[l[i]];
        for(auto j:intersection[i])
            AE(prvind,whatpos(j,y[i]),x[j]-prvpos),
            prvind=whatpos(j,y[i]),prvpos=x[j];
    }
    return djik(whatpos(s,0),whatpos(g,0));
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 42588 KB Output is correct
2 Correct 6 ms 42588 KB Output is correct
3 Correct 5 ms 42680 KB Output is correct
4 Correct 5 ms 42584 KB Output is correct
5 Runtime error 2073 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 42588 KB Output is correct
2 Correct 5 ms 42588 KB Output is correct
3 Runtime error 138 ms 122532 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 53976 KB Output is correct
2 Correct 721 ms 111040 KB Output is correct
3 Correct 592 ms 111080 KB Output is correct
4 Correct 535 ms 108492 KB Output is correct
5 Correct 627 ms 110532 KB Output is correct
6 Correct 605 ms 105648 KB Output is correct
7 Correct 232 ms 74952 KB Output is correct
8 Correct 142 ms 68292 KB Output is correct
9 Correct 603 ms 100632 KB Output is correct
10 Correct 287 ms 73768 KB Output is correct
11 Correct 12 ms 43416 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 53976 KB Output is correct
2 Correct 721 ms 111040 KB Output is correct
3 Correct 592 ms 111080 KB Output is correct
4 Correct 535 ms 108492 KB Output is correct
5 Correct 627 ms 110532 KB Output is correct
6 Correct 605 ms 105648 KB Output is correct
7 Correct 232 ms 74952 KB Output is correct
8 Correct 142 ms 68292 KB Output is correct
9 Correct 603 ms 100632 KB Output is correct
10 Correct 287 ms 73768 KB Output is correct
11 Correct 12 ms 43416 KB Output is correct
12 Correct 596 ms 111332 KB Output is correct
13 Correct 505 ms 109420 KB Output is correct
14 Correct 714 ms 113324 KB Output is correct
15 Correct 393 ms 99160 KB Output is correct
16 Correct 454 ms 98240 KB Output is correct
17 Correct 522 ms 109852 KB Output is correct
18 Correct 402 ms 99140 KB Output is correct
19 Correct 457 ms 98216 KB Output is correct
20 Correct 291 ms 76840 KB Output is correct
21 Correct 81 ms 49096 KB Output is correct
22 Correct 350 ms 95684 KB Output is correct
23 Correct 318 ms 92828 KB Output is correct
24 Correct 220 ms 78532 KB Output is correct
25 Correct 274 ms 88772 KB Output is correct
26 Correct 163 ms 70200 KB Output is correct
27 Correct 673 ms 112068 KB Output is correct
28 Correct 480 ms 108988 KB Output is correct
29 Correct 655 ms 105920 KB Output is correct
30 Correct 287 ms 78028 KB Output is correct
31 Correct 644 ms 103676 KB Output is correct
32 Correct 209 ms 72428 KB Output is correct
33 Correct 212 ms 70972 KB Output is correct
34 Correct 301 ms 77756 KB Output is correct
35 Correct 320 ms 79908 KB Output is correct
36 Correct 199 ms 73952 KB Output is correct
37 Correct 139 ms 70948 KB Output is correct
38 Correct 133 ms 68292 KB Output is correct
39 Correct 347 ms 82368 KB Output is correct
40 Correct 149 ms 70520 KB Output is correct
41 Correct 145 ms 70896 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 42588 KB Output is correct
2 Correct 6 ms 42588 KB Output is correct
3 Correct 5 ms 42680 KB Output is correct
4 Correct 5 ms 42584 KB Output is correct
5 Runtime error 2073 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -