oj.uz

Submission #1047081

# Submission time Handle Problem Language Result Execution time Memory
1047081 2024-08-07T08:41:32 Z vjudge1 Sky Walking (IOI19_walk) C++17
33 / 100
 716 ms 122548 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]);
        assert(*intersection[i].begin()>l[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 6 ms 42584 KB Output is correct
2 Correct 6 ms 42588 KB Output is correct
3 Correct 6 ms 42472 KB Output is correct
4 Correct 7 ms 42588 KB Output is correct
5 Runtime error 26 ms 73644 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 42584 KB Output is correct
2 Correct 5 ms 42588 KB Output is correct
3 Runtime error 140 ms 122548 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 65 ms 53800 KB Output is correct
2 Correct 673 ms 110884 KB Output is correct
3 Correct 601 ms 111056 KB Output is correct
4 Correct 540 ms 108220 KB Output is correct
5 Correct 647 ms 110528 KB Output is correct
6 Correct 583 ms 105664 KB Output is correct
7 Correct 231 ms 74780 KB Output is correct
8 Correct 144 ms 68408 KB Output is correct
9 Correct 623 ms 100596 KB Output is correct
10 Correct 302 ms 73756 KB Output is correct
11 Correct 11 ms 43416 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 53800 KB Output is correct
2 Correct 673 ms 110884 KB Output is correct
3 Correct 601 ms 111056 KB Output is correct
4 Correct 540 ms 108220 KB Output is correct
5 Correct 647 ms 110528 KB Output is correct
6 Correct 583 ms 105664 KB Output is correct
7 Correct 231 ms 74780 KB Output is correct
8 Correct 144 ms 68408 KB Output is correct
9 Correct 623 ms 100596 KB Output is correct
10 Correct 302 ms 73756 KB Output is correct
11 Correct 11 ms 43416 KB Output is correct
12 Correct 635 ms 111300 KB Output is correct
13 Correct 544 ms 109504 KB Output is correct
14 Correct 666 ms 113436 KB Output is correct
15 Correct 443 ms 99124 KB Output is correct
16 Correct 444 ms 98236 KB Output is correct
17 Correct 527 ms 110012 KB Output is correct
18 Correct 419 ms 98912 KB Output is correct
19 Correct 467 ms 98244 KB Output is correct
20 Correct 289 ms 76996 KB Output is correct
21 Correct 83 ms 49100 KB Output is correct
22 Correct 400 ms 95680 KB Output is correct
23 Correct 310 ms 92704 KB Output is correct
24 Correct 230 ms 78528 KB Output is correct
25 Correct 281 ms 88904 KB Output is correct
26 Correct 152 ms 70072 KB Output is correct
27 Correct 716 ms 112184 KB Output is correct
28 Correct 450 ms 108992 KB Output is correct
29 Correct 679 ms 105920 KB Output is correct
30 Correct 278 ms 78024 KB Output is correct
31 Correct 629 ms 103616 KB Output is correct
32 Correct 218 ms 72432 KB Output is correct
33 Correct 190 ms 71120 KB Output is correct
34 Correct 313 ms 77760 KB Output is correct
35 Correct 255 ms 80004 KB Output is correct
36 Correct 179 ms 73956 KB Output is correct
37 Correct 147 ms 70944 KB Output is correct
38 Correct 136 ms 68288 KB Output is correct
39 Correct 334 ms 82324 KB Output is correct
40 Correct 160 ms 70768 KB Output is correct
41 Correct 147 ms 70904 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 42584 KB Output is correct
2 Correct 6 ms 42588 KB Output is correct
3 Correct 6 ms 42472 KB Output is correct
4 Correct 7 ms 42588 KB Output is correct
5 Runtime error 26 ms 73644 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -