oj.uz

Submission #1046801

# Submission time Handle Problem Language Result Execution time Memory
1046801 2024-08-07T01:08:27 Z vjudge1 Sky Walking (IOI19_walk) C++17
0 / 100
 463 ms 131408 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;
}
int dis[1<<20];
long long djik(int a,int b){
    memset(dis,9,sizeof dis);
    priority_queue<pair<int,int>,vector<pair<int,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)thgs.push_back(p),
        hmm(l,p-1,x),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);
        sort(thgs.begin(),thgs.end());
        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34908 KB Output is correct
2 Correct 5 ms 34968 KB Output is correct
3 Incorrect 5 ms 34908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34908 KB Output is correct
2 Correct 4 ms 34908 KB Output is correct
3 Correct 463 ms 124312 KB Output is correct
4 Incorrect 328 ms 131408 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 45904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 45904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34908 KB Output is correct
2 Correct 5 ms 34968 KB Output is correct
3 Incorrect 5 ms 34908 KB Output isn't correct
4 Halted 0 ms 0 KB -