제출 #1046803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1046803		vjudge1	Sky Walking (IOI19_walk)	C++17	24 / 100	855 ms	334592 KiB

walk

#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));
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43