Submission #873682

#	Time	Username	Problem	Language	Result	Execution time	Memory
873682		andrei_boaca	Sky Walking (IOI19_walk)	C++17	10 / 100	645 ms	280000 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll INF=1e18;
int n;
int ind;
unordered_map<int,int> f[100005];
vector<pii> muchii[1000005];
vector<pii> nodes[1000005];
ll dist[1000005];
void addnode(int x,int y)
{
    if(f[x][y]!=0)
        return;
    ind++;
    f[x][y]=ind;
    nodes[x].push_back({y,ind});
}
bool use[1000005];
void bfs()
{
    for(int i=1;i<=ind;i++)
        dist[i]=INF;
    dist[1]=0;
    queue<pll> pq;
    pq.push({0,1});
    while(!pq.empty())
    {
        int nod=pq.front().second;
        pq.pop();
        if(use[nod])
            continue;
        use[nod]=1;
        for(auto i:muchii[nod])
            if(dist[i.first]>dist[nod]+i.second)
            {
                dist[i.first]=dist[nod]+i.second;
                pq.push({dist[i.first],i.first});
            }
    }
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g)
{
    n=x.size();
    addnode(s,0);
    addnode(g,0);
    for(int i=0;i<l.size();i++)
    {
        int prv=-1;
        for(int j=l[i];j<=r[i];j++)
            if(y[i]<=h[j])
            {
                addnode(j,y[i]);
                if(prv!=-1)
                {
                    int a=f[prv][y[i]];
                    int b=f[j][y[i]];
                    muchii[a].push_back({b,x[j]-x[prv]});
                    muchii[b].push_back({a,x[j]-x[prv]});
                }
                prv=j;
            }
    }
    for(int i=0;i<n;i++)
        if(!nodes[i].empty())
        {
            sort(nodes[i].begin(),nodes[i].end());
            for(int j=1;j<nodes[i].size();j++)
            {
                ll d=nodes[i][j].first-nodes[i][j-1].first;
                ll a=nodes[i][j].second;
                ll b=nodes[i][j-1].second;
                muchii[a].push_back({b,d});
                muchii[b].push_back({a,d});
            }
        }
    bfs();
    if(dist[2]==INF)
        return -1;
    return dist[2];
}

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:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<l.size();i++)
      |                 ~^~~~~~~~~
walk.cpp:75:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             for(int j=1;j<nodes[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~

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