제출 #901252

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

walk

#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&=(h[i]==h[0]);
    if (s>g)
        swap(s,g);
    if (s==0&&g==n-1&&ch){
        for (int i=0;i<m;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=ve.size()-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(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]+ve[0].second+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)]);
}

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

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:46: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]
   46 |         for (int i=0;i<=V.size();i++)
      |                      ~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43