Submission #293643

#	Time	Username	Problem	Language	Result	Execution time	Memory
293643		Autoratch	Sky Walking (IOI19_walk)	C++14	10 / 100	4067 ms	363128 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<long long,int> 

const int N = 1.5e6 + 1;

int n,m,id;
pair<int,int> val[N];
vector<pair<int,int> > ver[N];
vector<pair<long long,int> > adj[N];
long long dist[N];
bool visited[N];
priority_queue<pii,vector<pii>,greater<pii> > q;

long long min_distance(vector<int> x,vector<int> h,vector<int> l,vector<int> r,vector<int> y,int s,int g) 
{
    n = x.size(),m = l.size();
    for(int i = 0;i < n;i++)
    {
        ver[i].push_back({0,i});
        val[i] = {i,0};
        id++;
    }
    id++;
    for(int i = 0;i < m;i++)
    {
        vector<int> wo;
        for(int j = l[i];j <= r[i];j++) if(h[j]>=y[i]) wo.push_back(j);
        int pr = -1;
        for(int j : wo) 
        {
            val[++id] = {j,y[i]};
            if(pr!=-1)
            {
                adj[id].push_back({x[j]-x[pr],id-1});
                adj[id-1].push_back({x[j]-x[pr],id});
            }
            pr = j;
            ver[j].push_back({y[i],id});
        }
    }
    for(int i = 0;i < n;i++)
    {
        sort(ver[i].begin(),ver[i].end());
        for(int j = 1;j < ver[i].size();j++)
        {
            adj[ver[i][j-1].second].push_back({ver[i][j].first-ver[i][j-1].first,ver[i][j].second});
            adj[ver[i][j].second].push_back({ver[i][j].first-ver[i][j-1].first,ver[i][j-1].second});
        }
    }
    for(int i = 0;i <= id;i++) dist[i] = LLONG_MAX;
    dist[s] = 0;
    q.push({0,s});
    while(!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if(visited[u]) continue;
        visited[u] = true;
        for(auto [w,v] : adj[u]) if(dist[u]+w<dist[v]) dist[v] = dist[u]+w,q.push({dist[v],v});
    }
    if(dist[g]==LLONG_MAX) dist[g] = -1;
    return dist[g];
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:46:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int j = 1;j < ver[i].size();j++)
      |                       ~~^~~~~~~~~~~~~~~
walk.cpp:61:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |         for(auto [w,v] : adj[u]) if(dist[u]+w<dist[v]) dist[v] = dist[u]+w,q.push({dist[v],v});
      |                  ^

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