Submission #992306

#	Time	Username	Problem	Language	Result	Execution time	Memory
992306		amine_aroua	Sky Walking (IOI19_walk)	C++17	Compilation error	0 ms	0 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++)

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();
    gp_hash_table<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());
    gp_hash_table<pair<int ,int> , vector<pair<pair<int , int> , int>>> adj;
    fore(i , n)
    {
        degs[i][0] = i;
    }
    for(auto [Y , L , R] : lines)
    {
        forr(i , L , R)
        {
            degs[i][Y] = max(degs[i][Y] , R);
        }
    }
    gp_hash_table<pair<int , int> , Int> dist;
    fore(i , n)
    {
        if(degs[i].empty())
            continue;
        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 , pair<int , int>> , int> vis;
    dist[{0 , 0}] = 0;
    while(!pq.empty())
    {
        auto tp = pq.top();
        pq.pop();
        if(vis[tp] == 1)
            continue;
        vis[tp] = 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 -1;
    }
    return dist[{n - 1 , 0}] + x[n - 1] - x[0];
}
int 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;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccegsSZD.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccD9kpFC.o:walk.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccD9kpFC.o: in function `min_distance(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)':
walk.cpp:(.text+0x19f8): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: walk.cpp:(.text+0x24d8): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: walk.cpp:(.text+0x26f1): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: walk.cpp:(.text+0x2934): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: walk.cpp:(.text+0x2fd6): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: /tmp/ccD9kpFC.o:walk.cpp:(.text+0x31d3): more undefined references to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const' follow
collect2: error: ld returned 1 exit status