oj.uz

Submission #1046803

# Submission time Handle Problem Language Result Execution time Memory
1046803 2024-08-07T01:12:40 Z vjudge1 Sky Walking (IOI19_walk) C++17
24 / 100
 855 ms 334592 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;
}
VI thgs;
pair<int,int> stb[100100][20];
pair<int,int> qry(int l,int r){
    int x=31-__builtin_clz(r-l+1);
    return max(stb[l][x],stb[r-(1<<x)+1][x]);
}
void hmm(int l,int r,int x){
    if(r<l) return;
    auto[h,p]=qry(l,r);
    if(h>=x)hmm(l,p-1,x),
        thgs.push_back(p),hmm(p+1,r,x);
}
long long min_distance(VI x,VI h,VI l,VI r,VI y,int s,int g) {
    int n=x.size();
    for(int i=0;i<n;i++)
        stb[i][0]={h[i],i};
    for(int j=1;j<20;j++)for(int i=0;i+(1<<j)<=n;i++)
        stb[i][j]=max(stb[i][j-1],stb[i+(1<<j-1)][j-1]);
    int m=l.size();
    for(int i=0;i<m;i++){
        int u=l[i],v=r[i],k=y[i];
        int prvind=whatpos(u,k),prvpos=x[u];
        hmm(u+1,v,k);
        for(auto i:thgs)
            AE(prvind,whatpos(i,k),x[i]-prvpos),
            prvind=whatpos(i,k),prvpos=x[i];
        thgs.clear();
    }
    return djik(whatpos(s,0),whatpos(g,0));
}

Compilation message

walk.cpp: In function 'long long int min_distance(VI, VI, VI, VI, VI, int, int)':
walk.cpp:56:46: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   56 |         stb[i][j]=max(stb[i][j-1],stb[i+(1<<j-1)][j-1]);
      |                                             ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39004 KB Output is correct
2 Correct 5 ms 39004 KB Output is correct
3 Correct 5 ms 39004 KB Output is correct
4 Correct 7 ms 39004 KB Output is correct
5 Correct 6 ms 39092 KB Output is correct
6 Correct 5 ms 39004 KB Output is correct
7 Correct 5 ms 39004 KB Output is correct
8 Correct 5 ms 39004 KB Output is correct
9 Correct 6 ms 39004 KB Output is correct
10 Correct 6 ms 39000 KB Output is correct
11 Correct 6 ms 39000 KB Output is correct
12 Correct 5 ms 39004 KB Output is correct
13 Correct 5 ms 39004 KB Output is correct
14 Correct 5 ms 39004 KB Output is correct
15 Correct 5 ms 39000 KB Output is correct
16 Correct 5 ms 39004 KB Output is correct
17 Correct 5 ms 39004 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39000 KB Output is correct
2 Correct 5 ms 39004 KB Output is correct
3 Correct 607 ms 126592 KB Output is correct
4 Correct 428 ms 131368 KB Output is correct
5 Correct 242 ms 122904 KB Output is correct
6 Correct 221 ms 113744 KB Output is correct
7 Correct 244 ms 122968 KB Output is correct
8 Correct 855 ms 153436 KB Output is correct
9 Correct 298 ms 124500 KB Output is correct
10 Correct 668 ms 171344 KB Output is correct
11 Correct 228 ms 87892 KB Output is correct
12 Correct 122 ms 77156 KB Output is correct
13 Correct 543 ms 154964 KB Output is correct
14 Correct 83 ms 76364 KB Output is correct
15 Correct 96 ms 76372 KB Output is correct
16 Correct 104 ms 77908 KB Output is correct
17 Correct 98 ms 76864 KB Output is correct
18 Correct 175 ms 84992 KB Output is correct
19 Correct 8 ms 42328 KB Output is correct
20 Correct 31 ms 58716 KB Output is correct
21 Correct 95 ms 74772 KB Output is correct
22 Correct 93 ms 76116 KB Output is correct
23 Correct 167 ms 83148 KB Output is correct
24 Correct 109 ms 77208 KB Output is correct
25 Correct 95 ms 76524 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 48984 KB Output is correct
2 Runtime error 565 ms 334592 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 48984 KB Output is correct
2 Runtime error 565 ms 334592 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39004 KB Output is correct
2 Correct 5 ms 39004 KB Output is correct
3 Correct 5 ms 39004 KB Output is correct
4 Correct 7 ms 39004 KB Output is correct
5 Correct 6 ms 39092 KB Output is correct
6 Correct 5 ms 39004 KB Output is correct
7 Correct 5 ms 39004 KB Output is correct
8 Correct 5 ms 39004 KB Output is correct
9 Correct 6 ms 39004 KB Output is correct
10 Correct 6 ms 39000 KB Output is correct
11 Correct 6 ms 39000 KB Output is correct
12 Correct 5 ms 39004 KB Output is correct
13 Correct 5 ms 39004 KB Output is correct
14 Correct 5 ms 39004 KB Output is correct
15 Correct 5 ms 39000 KB Output is correct
16 Correct 5 ms 39004 KB Output is correct
17 Correct 5 ms 39004 KB Output is correct
18 Correct 5 ms 39000 KB Output is correct
19 Correct 5 ms 39004 KB Output is correct
20 Correct 607 ms 126592 KB Output is correct
21 Correct 428 ms 131368 KB Output is correct
22 Correct 242 ms 122904 KB Output is correct
23 Correct 221 ms 113744 KB Output is correct
24 Correct 244 ms 122968 KB Output is correct
25 Correct 855 ms 153436 KB Output is correct
26 Correct 298 ms 124500 KB Output is correct
27 Correct 668 ms 171344 KB Output is correct
28 Correct 228 ms 87892 KB Output is correct
29 Correct 122 ms 77156 KB Output is correct
30 Correct 543 ms 154964 KB Output is correct
31 Correct 83 ms 76364 KB Output is correct
32 Correct 96 ms 76372 KB Output is correct
33 Correct 104 ms 77908 KB Output is correct
34 Correct 98 ms 76864 KB Output is correct
35 Correct 175 ms 84992 KB Output is correct
36 Correct 8 ms 42328 KB Output is correct
37 Correct 31 ms 58716 KB Output is correct
38 Correct 95 ms 74772 KB Output is correct
39 Correct 93 ms 76116 KB Output is correct
40 Correct 167 ms 83148 KB Output is correct
41 Correct 109 ms 77208 KB Output is correct
42 Correct 95 ms 76524 KB Output is correct
43 Correct 33 ms 48984 KB Output is correct
44 Runtime error 565 ms 334592 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -