oj.uz

Submission #1047076

# Submission time Handle Problem Language Result Execution time Memory
1047076 2024-08-07T08:37:04 Z vjudge1 Sky Walking (IOI19_walk) C++17
33 / 100
 2195 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++)
        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++){
        intersection[i].insert(r[i]);
        intersection[i].erase(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 42588 KB Output is correct
2 Correct 6 ms 42672 KB Output is correct
3 Correct 7 ms 42444 KB Output is correct
4 Correct 5 ms 42588 KB Output is correct
5 Runtime error 2195 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 8 ms 42588 KB Output is correct
2 Correct 7 ms 42584 KB Output is correct
3 Runtime error 160 ms 124516 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 84 ms 54556 KB Output is correct
2 Correct 750 ms 112832 KB Output is correct
3 Correct 696 ms 113132 KB Output is correct
4 Correct 576 ms 112252 KB Output is correct
5 Correct 688 ms 114436 KB Output is correct
6 Correct 672 ms 109764 KB Output is correct
7 Correct 249 ms 77764 KB Output is correct
8 Correct 160 ms 72384 KB Output is correct
9 Correct 661 ms 104712 KB Output is correct
10 Correct 331 ms 77252 KB Output is correct
11 Correct 26 ms 44332 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 54556 KB Output is correct
2 Correct 750 ms 112832 KB Output is correct
3 Correct 696 ms 113132 KB Output is correct
4 Correct 576 ms 112252 KB Output is correct
5 Correct 688 ms 114436 KB Output is correct
6 Correct 672 ms 109764 KB Output is correct
7 Correct 249 ms 77764 KB Output is correct
8 Correct 160 ms 72384 KB Output is correct
9 Correct 661 ms 104712 KB Output is correct
10 Correct 331 ms 77252 KB Output is correct
11 Correct 26 ms 44332 KB Output is correct
12 Correct 675 ms 113420 KB Output is correct
13 Correct 545 ms 113608 KB Output is correct
14 Correct 783 ms 117444 KB Output is correct
15 Correct 452 ms 102948 KB Output is correct
16 Correct 534 ms 102236 KB Output is correct
17 Correct 574 ms 113904 KB Output is correct
18 Correct 459 ms 102812 KB Output is correct
19 Correct 476 ms 102404 KB Output is correct
20 Correct 288 ms 79852 KB Output is correct
21 Correct 83 ms 51140 KB Output is correct
22 Correct 368 ms 99492 KB Output is correct
23 Correct 337 ms 96732 KB Output is correct
24 Correct 234 ms 82524 KB Output is correct
25 Correct 308 ms 92612 KB Output is correct
26 Correct 167 ms 73864 KB Output is correct
27 Correct 669 ms 116164 KB Output is correct
28 Correct 447 ms 113000 KB Output is correct
29 Correct 703 ms 110028 KB Output is correct
30 Correct 330 ms 81092 KB Output is correct
31 Correct 624 ms 107508 KB Output is correct
32 Correct 211 ms 75504 KB Output is correct
33 Correct 218 ms 74436 KB Output is correct
34 Correct 341 ms 80840 KB Output is correct
35 Correct 301 ms 83224 KB Output is correct
36 Correct 213 ms 77024 KB Output is correct
37 Correct 161 ms 73760 KB Output is correct
38 Correct 163 ms 71616 KB Output is correct
39 Correct 359 ms 85232 KB Output is correct
40 Correct 202 ms 73444 KB Output is correct
41 Correct 153 ms 73720 KB Output is correct

Subtask #5
0 / 43.0

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