oj.uz

Submission #901234

# Submission time Handle Problem Language Result Execution time Memory
901234 2024-01-09T08:10:47 Z abcvuitunggio Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 878780 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 <pair <int, int>> ke[12000001],ve,nodes;
int n,m,d[12000001],dp[200001],ft[200001][2];
set <int> S;
void add(int i, int j){
    a[i].push_back(j);
    nodes.push_back({i,j});
}
int f(int i, int j){
    return lower_bound(nodes.begin(),nodes.end(),make_pair(i,j))-nodes.begin();
}
void update(int i, int j, int val){
    for (;i<=V.size();i+=i&(-i))
        ft[i][j]=min(ft[i][j],val);
}
int get(int i, int j){
    int res=INF;
    for (;i;i-=i&(-i))
        res=min(res,ft[i][j]);
    return res;
}
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){
    n=x.size(),m=l.size();
    int ch=1;
    for (int i=1;i<n;i++)
        ch&=(x[i]==x[0]);
    if (s==0&&g==n-1&&ch){
        for (int i=0;i<n;i++){
            ve.push_back({l[i],y[i]});
            if (r[i]==g)
                ve.push_back({r[i],y[i]});
        }
        sort(ve.begin(),ve.end());
        for (auto [i,j]:ve)
            V.push_back(j);
        sort(V.begin(),V.end());
        V.resize(unique(V.begin(),V.end())-V.begin());
        for (int i=0;i<=V.size();i++)
            ft[i][0]=ft[i][1]=INF;
        for (int i=n-1;i>=0;i--){
            int Y=ve[i].second,j=lower_bound(V.begin(),V.end(),Y)-V.begin()+1;
            if (ve[i].first==g)
                dp[i]=Y;
            else
                //dp[i]=min(dp[j]+abs(y[i]-y[j]))
                dp[i]=min(get(V.size()-j+1,0)-Y,get(j,1)+Y);
            update(V.size()-j+1,0,dp[i]+Y);
            update(j,1,dp[i]-Y);
        }
        return dp[0]+x[g]-x[s];
    }
    for (int i=0;i<n;i++)
        ve.push_back({-h[i],-i});
    for (int i=0;i<m;i++)
        ve.push_back({-y[i],i+1});
    sort(ve.begin(),ve.end());
    for (auto [i,j]:ve){
        i=-i,j=-j;
        if (j>=0){
            S.insert(j);
            continue;
        }
        j=-j-1;
        for (auto it=S.lower_bound(l[j]);it!=S.end()&&*it<=r[j];it++){
            add(*it,j);
            b[j].push_back(*it);
        }
    }
    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=abs((a[i][j]>=0?y[a[i][j]]:0)-(a[i][j+1]>=0?y[a[i][j+1]]:0));
            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]];
            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 update(long long int, long long int, long long int)':
walk.cpp:19:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (;i<=V.size();i+=i&(-i))
      |           ~^~~~~~~~~~
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int32_t, int32_t)':
walk.cpp:44:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int i=0;i<=V.size();i++)
      |                      ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 290852 KB Output is correct
2 Correct 66 ms 290780 KB Output is correct
3 Correct 62 ms 290900 KB Output is correct
4 Correct 62 ms 290924 KB Output is correct
5 Correct 63 ms 290900 KB Output is correct
6 Correct 71 ms 290900 KB Output is correct
7 Correct 72 ms 290904 KB Output is correct
8 Correct 62 ms 290904 KB Output is correct
9 Correct 62 ms 290856 KB Output is correct
10 Correct 73 ms 291036 KB Output is correct
11 Correct 65 ms 290900 KB Output is correct
12 Correct 66 ms 290796 KB Output is correct
13 Correct 70 ms 290900 KB Output is correct
14 Correct 62 ms 290900 KB Output is correct
15 Correct 63 ms 290896 KB Output is correct
16 Correct 63 ms 290896 KB Output is correct
17 Correct 66 ms 290892 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 290976 KB Output is correct
2 Correct 64 ms 290848 KB Output is correct
3 Correct 1171 ms 392048 KB Output is correct
4 Correct 1090 ms 395624 KB Output is correct
5 Correct 752 ms 382896 KB Output is correct
6 Correct 684 ms 372032 KB Output is correct
7 Correct 793 ms 382460 KB Output is correct
8 Correct 1475 ms 423316 KB Output is correct
9 Correct 973 ms 385668 KB Output is correct
10 Correct 1538 ms 443988 KB Output is correct
11 Correct 535 ms 348776 KB Output is correct
12 Correct 392 ms 326600 KB Output is correct
13 Correct 1281 ms 426184 KB Output is correct
14 Correct 304 ms 325940 KB Output is correct
15 Correct 354 ms 326028 KB Output is correct
16 Correct 340 ms 331068 KB Output is correct
17 Correct 307 ms 326084 KB Output is correct
18 Correct 347 ms 335548 KB Output is correct
19 Correct 67 ms 292556 KB Output is correct
20 Correct 130 ms 307512 KB Output is correct
21 Correct 329 ms 326420 KB Output is correct
22 Correct 333 ms 325460 KB Output is correct
23 Correct 381 ms 336024 KB Output is correct
24 Correct 353 ms 326564 KB Output is correct
25 Correct 301 ms 326588 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 307512 KB Output is correct
2 Execution timed out 4086 ms 878780 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 307512 KB Output is correct
2 Execution timed out 4086 ms 878780 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 290852 KB Output is correct
2 Correct 66 ms 290780 KB Output is correct
3 Correct 62 ms 290900 KB Output is correct
4 Correct 62 ms 290924 KB Output is correct
5 Correct 63 ms 290900 KB Output is correct
6 Correct 71 ms 290900 KB Output is correct
7 Correct 72 ms 290904 KB Output is correct
8 Correct 62 ms 290904 KB Output is correct
9 Correct 62 ms 290856 KB Output is correct
10 Correct 73 ms 291036 KB Output is correct
11 Correct 65 ms 290900 KB Output is correct
12 Correct 66 ms 290796 KB Output is correct
13 Correct 70 ms 290900 KB Output is correct
14 Correct 62 ms 290900 KB Output is correct
15 Correct 63 ms 290896 KB Output is correct
16 Correct 63 ms 290896 KB Output is correct
17 Correct 66 ms 290892 KB Output is correct
18 Correct 64 ms 290976 KB Output is correct
19 Correct 64 ms 290848 KB Output is correct
20 Correct 1171 ms 392048 KB Output is correct
21 Correct 1090 ms 395624 KB Output is correct
22 Correct 752 ms 382896 KB Output is correct
23 Correct 684 ms 372032 KB Output is correct
24 Correct 793 ms 382460 KB Output is correct
25 Correct 1475 ms 423316 KB Output is correct
26 Correct 973 ms 385668 KB Output is correct
27 Correct 1538 ms 443988 KB Output is correct
28 Correct 535 ms 348776 KB Output is correct
29 Correct 392 ms 326600 KB Output is correct
30 Correct 1281 ms 426184 KB Output is correct
31 Correct 304 ms 325940 KB Output is correct
32 Correct 354 ms 326028 KB Output is correct
33 Correct 340 ms 331068 KB Output is correct
34 Correct 307 ms 326084 KB Output is correct
35 Correct 347 ms 335548 KB Output is correct
36 Correct 67 ms 292556 KB Output is correct
37 Correct 130 ms 307512 KB Output is correct
38 Correct 329 ms 326420 KB Output is correct
39 Correct 333 ms 325460 KB Output is correct
40 Correct 381 ms 336024 KB Output is correct
41 Correct 353 ms 326564 KB Output is correct
42 Correct 301 ms 326588 KB Output is correct
43 Correct 169 ms 307512 KB Output is correct
44 Execution timed out 4086 ms 878780 KB Time limit exceeded
45 Halted 0 ms 0 KB -