oj.uz

Submission #902103

# Submission time Handle Problem Language Result Execution time Memory
902103 2024-01-10T06:03:38 Z abcvuitunggio Sky Walking (IOI19_walk) C++17
43 / 100
 906 ms 103604 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e18;
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q;
vector <int> a[100001],b[100001],V;
vector <int32_t> x,h,l,r,y;
vector <pair <int, int>> ke[1000001],ve;
vector <pair <int32_t, int32_t>> nodes;
int n,m,d[1000001];
set <int> S;
void add(int i, int j){
    a[i].push_back(j);
    nodes.push_back({x[i],(j==-1?0:y[j])});
}
int f(int i, int j){
    return lower_bound(nodes.begin(),nodes.end(),make_pair(x[i],(j==-1?0:y[j])))-nodes.begin();
}
void reconnect(int32_t s, int mode){
    vector <pair <int32_t, int32_t>> tmp,changes;
    for (int i=s;(mode?i<n:i>=0);i+=mode*2-1)
        if (tmp.empty()||h[i]>tmp.back().first)
            tmp.push_back({h[i],i});
    for (int i=0;i<l.size();i++)
        if (l[i]<s&&s<r[i]){
            auto a=tmp[lower_bound(tmp.begin(),tmp.end(),make_pair(y[i],-1))-tmp.begin()];
            changes.push_back({i,a.second});
        }
    for (auto [i,j]:changes){
        if (j==l[i]||j==r[i])
            continue;
        if (mode)
            swap(l,r);
        l.push_back(j);
        r.push_back(r[i]);
        y.push_back(y[i]);
        r[i]=j;
        if (mode)
            swap(l,r);
    }
}
int 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){
    x=X,h=H,l=L,r=R,y=Y,n=x.size();
    if (s>g)
        swap(s,g);
    reconnect(s,0);
    reconnect(s,1);
    reconnect(g,0);
    reconnect(g,1);
    m=l.size();
    for (int i=0;i<m;i++){
        ve.push_back({l[i],i});
        ve.push_back({r[i],i});
    }
    sort(ve.begin(),ve.end(),[](pair <int, int> a, pair <int, int> b){
            if (a.first!=b.first)
                return a.first<b.first;
            bool p=(a.first==r[a.second]),q=(b.first==r[b.second]);
            if (p!=q)
                return p<q;
            if (p)
                return y[a.second]>y[b.second];
            return y[a.second]<y[b.second];
         });
    set <pair <int, int>> cur;
    for (auto [i,j]:ve){
        add(i,j);
        b[j].push_back(i);
        if (i==l[j])
            cur.insert({y[j],j});
        else
            cur.erase({y[j],j});
        if (!cur.empty()){
            auto it=cur.lower_bound(make_pair(y[j],-1));
            if (it!=cur.begin()){
                it--;
                add(i,(*it).second);
                b[(*it).second].push_back(i);
            }
        }
    }
    for (int i=0;i<n;i++)
        sort(a[i].begin(),a[i].end(),[](int i, int j){return y[i]>y[j];});
    for (int i=0;i<m;i++)
        sort(b[i].begin(),b[i].end(),[](int i, int j){return x[i]<x[j];});
    add(s,-1);
    add(g,-1);
    sort(nodes.begin(),nodes.end());
    nodes.resize(unique(nodes.begin(),nodes.end())-nodes.begin());
    for (int i=0;i<n;i++)
        for (int j=0;j<(int)a[i].size()-1;j++){
            int u=f(i,a[i][j]),v=f(i,a[i][j+1]),w=(a[i][j]>=0?y[a[i][j]]:0)-(a[i][j+1]>=0?y[a[i][j+1]]:0);
            if (u==v)
                continue;
            ke[u].push_back({v,w});
            ke[v].push_back({u,w});
        }
    for (int i=0;i<m;i++)
        for (int j=0;j<(int)b[i].size()-1;j++){
            int u=f(b[i][j],i),v=f(b[i][j+1],i),w=x[b[i][j+1]]-x[b[i][j]];
            if (u==v)
                continue;
            ke[u].push_back({v,w});
            ke[v].push_back({u,w});
        }
    fill(d,d+nodes.size(),INF);
    d[f(s,-1)]=0;
    q.push({0,f(s,-1)});
    while (!q.empty()){
        auto [du,u]=q.top();
        q.pop();
        if (du!=d[u])
            continue;
        for (auto [v,w]:ke[u])
            if (d[v]>d[u]+w){
                d[v]=d[u]+w;
                q.push({d[v],v});
            }
    }
    return (d[f(g,-1)]==INF?-1:d[f(g,-1)]);
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 30044 KB Output is correct
2 Correct 8 ms 30044 KB Output is correct
3 Correct 6 ms 30040 KB Output is correct
4 Correct 6 ms 30044 KB Output is correct
5 Correct 7 ms 30044 KB Output is correct
6 Correct 7 ms 30044 KB Output is correct
7 Correct 7 ms 30088 KB Output is correct
8 Correct 7 ms 30044 KB Output is correct
9 Correct 6 ms 30056 KB Output is correct
10 Correct 7 ms 30052 KB Output is correct
11 Correct 7 ms 30048 KB Output is correct
12 Correct 7 ms 30128 KB Output is correct
13 Correct 7 ms 30052 KB Output is correct
14 Correct 6 ms 30052 KB Output is correct
15 Correct 7 ms 30056 KB Output is correct
16 Correct 7 ms 30048 KB Output is correct
17 Correct 7 ms 30056 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 30052 KB Output is correct
2 Correct 6 ms 30048 KB Output is correct
3 Runtime error 156 ms 103604 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 114 ms 47308 KB Output is correct
2 Correct 589 ms 91272 KB Output is correct
3 Correct 619 ms 92360 KB Output is correct
4 Correct 667 ms 95368 KB Output is correct
5 Correct 782 ms 99916 KB Output is correct
6 Correct 687 ms 94752 KB Output is correct
7 Correct 269 ms 63680 KB Output is correct
8 Correct 267 ms 68232 KB Output is correct
9 Correct 705 ms 92532 KB Output is correct
10 Correct 350 ms 69944 KB Output is correct
11 Correct 15 ms 32088 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 47308 KB Output is correct
2 Correct 589 ms 91272 KB Output is correct
3 Correct 619 ms 92360 KB Output is correct
4 Correct 667 ms 95368 KB Output is correct
5 Correct 782 ms 99916 KB Output is correct
6 Correct 687 ms 94752 KB Output is correct
7 Correct 269 ms 63680 KB Output is correct
8 Correct 267 ms 68232 KB Output is correct
9 Correct 705 ms 92532 KB Output is correct
10 Correct 350 ms 69944 KB Output is correct
11 Correct 15 ms 32088 KB Output is correct
12 Correct 664 ms 93624 KB Output is correct
13 Correct 537 ms 93340 KB Output is correct
14 Correct 906 ms 99888 KB Output is correct
15 Correct 501 ms 87584 KB Output is correct
16 Correct 514 ms 90064 KB Output is correct
17 Correct 525 ms 94056 KB Output is correct
18 Correct 517 ms 87872 KB Output is correct
19 Correct 520 ms 91216 KB Output is correct
20 Correct 277 ms 63164 KB Output is correct
21 Correct 32 ms 34864 KB Output is correct
22 Correct 420 ms 84248 KB Output is correct
23 Correct 403 ms 82436 KB Output is correct
24 Correct 295 ms 71588 KB Output is correct
25 Correct 315 ms 79292 KB Output is correct
26 Correct 246 ms 67448 KB Output is correct
27 Correct 798 ms 99260 KB Output is correct
28 Correct 453 ms 93056 KB Output is correct
29 Correct 763 ms 96084 KB Output is correct
30 Correct 275 ms 63532 KB Output is correct
31 Correct 737 ms 94144 KB Output is correct
32 Correct 327 ms 69992 KB Output is correct
33 Correct 277 ms 67812 KB Output is correct
34 Correct 372 ms 71388 KB Output is correct
35 Correct 352 ms 72804 KB Output is correct
36 Correct 278 ms 70888 KB Output is correct
37 Correct 277 ms 69852 KB Output is correct
38 Correct 251 ms 65724 KB Output is correct
39 Correct 399 ms 74172 KB Output is correct
40 Correct 277 ms 67948 KB Output is correct
41 Correct 308 ms 68540 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 30044 KB Output is correct
2 Correct 8 ms 30044 KB Output is correct
3 Correct 6 ms 30040 KB Output is correct
4 Correct 6 ms 30044 KB Output is correct
5 Correct 7 ms 30044 KB Output is correct
6 Correct 7 ms 30044 KB Output is correct
7 Correct 7 ms 30088 KB Output is correct
8 Correct 7 ms 30044 KB Output is correct
9 Correct 6 ms 30056 KB Output is correct
10 Correct 7 ms 30052 KB Output is correct
11 Correct 7 ms 30048 KB Output is correct
12 Correct 7 ms 30128 KB Output is correct
13 Correct 7 ms 30052 KB Output is correct
14 Correct 6 ms 30052 KB Output is correct
15 Correct 7 ms 30056 KB Output is correct
16 Correct 7 ms 30048 KB Output is correct
17 Correct 7 ms 30056 KB Output is correct
18 Correct 6 ms 30052 KB Output is correct
19 Correct 6 ms 30048 KB Output is correct
20 Runtime error 156 ms 103604 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -