Submission #992344

#	Time	Username	Problem	Language	Result	Execution time	Memory
992344		amine_aroua	Sky Walking (IOI19_walk)	C++17	0 / 100	4082 ms	910136 KiB

walk

#include <cstdio>
#include <cassert>
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace __gnu_pbds;
using namespace std;
#define Int long long
#define pb push_back
#define fore(i , m) for(int i = 0 ; i < m ; i++)
#define forn(i , x , y) for(int i = x ; i >= y;i--)
#define forr(i , x , y) for(int i = x ; i <= y; i++)
struct chash {
    Int operator()(pair<Int ,Int> x) const { return x.first* 31ll + x.second; }
};
const Int INF = 1e18;
 
Int min_distance(vector<int> x, vector<int> h , vector<int> l , vector<int> r , vector<int> y , int s , int g)
{
    int m = (Int)l.size();
    int n = (Int)x.size();
    map<Int , Int> degs[n];
    vector<tuple<Int ,Int,Int>> lines;
    fore(i , m)
    {
        lines.pb({y[i] , l[i] , r[i]});
    }
    sort(lines.begin() , lines.end());
    map<pair<Int ,Int> , vector<pair<pair<Int , Int> , Int>> > adj;
    fore(i , n)
    {
        degs[i][0] = i;
    }
    vector<Int> mxR(n , 0);
    for(auto [Y , L , R] : lines)
    {
        forr(i , L , R)
        {
            degs[i][Y] = max(degs[i][Y] , R);
            mxR[i] = max(mxR[i] , R);
        }
    }
    fore(i , n - 1)
    {
        if(mxR[i] <= i)
        {
            return -1ll;
        }
    }
    map<pair<Int , Int> , Int > dist;
    fore(i , n)
    {
        if(degs[i].empty())
        {
            return -1ll;
        }
        for(auto it = degs[i].begin() ; it != (degs[i].end()) ; it++)
        {
            auto [Y , R] = *it;
            dist[{i , Y}] = INF;
            if(R >= i + 1 && Y != 0)
            {
                adj[{i , Y}].pb({{i + 1 , Y} , 0});
            }
            if(it == prev(degs[i].end()))
                break;
            auto [nY , nR] = *next(it);
            adj[{i , Y}].pb({{i , nY} , nY - Y});
            adj[{i , nY}].pb({{i , Y} , nY - Y});
        }
    }
    priority_queue<pair<Int , pair<Int , Int>>> pq;
    pq.push({0 , {0 , 0}});
    map<pair<Int , Int> , Int > vis;
    dist[{0 , 0}] = 0;
    while(!pq.empty())
    {
        auto tp = pq.top();
        pq.pop();
        if(vis[tp.second] == 1)
            continue;
        vis[tp.second] = 1;
        auto [i , Y] = tp.second;
        for(auto p : adj[{i , Y}])
        {
            Int w = p.second;
            auto [j , nY] = p.first;
            if(dist[{j , nY}] > dist[{i , Y}] + w)
            {
                pq.push({-dist[{i , Y}] - w , {j , nY}});
                dist[{j , nY}] = w + dist[{i , Y}];
            }
        }
    }
    if(dist[{n - 1 , 0}] >= INF)
    {
        return -1ll;
    }
    return dist[{n - 1 , 0}] + x[n - 1] - x[0];
}
//signed main() {
//    int n, m;
//    assert(2 == scanf("%d%d", &n, &m));
//    vector<int> x(n), h(n);
//    for (int i = 0; i < n; i++)
//        assert(2 == scanf("%d%d", &x[i], &h[i]));
//    vector<int> l(m), r(m), y(m);
//    for (int i = 0; i < m; i++)
//        assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
//    int s, g;
//    assert(2 == scanf("%d%d", &s, &g));
//    fclose(stdin);
//
//    long long result = min_distance(x, h, l, r, y, s, g);
//
//    printf("%lld\n", result);
//    fclose(stdout);
//    return 0;
//}

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