답안 #992300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
992300	2024-06-04T08:58:47 Z	amine_aroua	Sky Walking (IOI19_walk)	C++17	컴파일 오류	0 ms	0 KB

walk

#include <cstdio>
#include <cassert>
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
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();
    int H = h[0];
    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}});
    gp_hash_table<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

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:19:9: warning: unused variable 'H' [-Wunused-variable]
   19 |     int H = h[0];
      |         ^
/usr/bin/ld: /tmp/ccrLjMWf.o: in function `__gnu_pbds::detail::gp_ht_map<std::pair<int, int>, long long, std::tr1::hash<std::pair<int, int> >, std::equal_to<std::pair<int, int> >, std::allocator<char>, false, __gnu_pbds::direct_mask_range_hashing<unsigned long>, __gnu_pbds::linear_probe_fn<unsigned long>, __gnu_pbds::hash_standard_resize_policy<__gnu_pbds::hash_exponential_size_policy<unsigned long>, __gnu_pbds::hash_load_check_resize_trigger<false, unsigned long>, false, unsigned long> >::subscript_imp(std::pair<int, int> const&, std::tr1::integral_constant<int, 0>) [clone .isra.0]':
walk.cpp:(.text+0x759): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: walk.cpp:(.text+0x87d): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: /tmp/ccrLjMWf.o: in function `__gnu_pbds::detail::gp_ht_map<std::pair<int, int>, std::vector<std::pair<std::pair<int, int>, int>, std::allocator<std::pair<std::pair<int, int>, int> > >, std::tr1::hash<std::pair<int, int> >, std::equal_to<std::pair<int, int> >, std::allocator<char>, false, __gnu_pbds::direct_mask_range_hashing<unsigned long>, __gnu_pbds::linear_probe_fn<unsigned long>, __gnu_pbds::hash_standard_resize_policy<__gnu_pbds::hash_exponential_size_policy<unsigned long>, __gnu_pbds::hash_load_check_resize_trigger<false, unsigned long>, false, unsigned long> >::subscript_imp(std::pair<int, int> const&, std::tr1::integral_constant<int, 0>) [clone .isra.0]':
walk.cpp:(.text+0x95b): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: walk.cpp:(.text+0xb9b): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: /tmp/ccrLjMWf.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+0x176e): undefined reference to `std::tr1::hash<std::pair<long long, std::pair<int, int> > >::operator()(std::pair<long long, std::pair<int, int> >) const'
/usr/bin/ld: walk.cpp:(.text+0x1a23): undefined reference to `std::tr1::hash<std::pair<long long, std::pair<int, int> > >::operator()(std::pair<long long, std::pair<int, int> >) const'
/usr/bin/ld: walk.cpp:(.text+0x1eaa): undefined reference to `std::tr1::hash<std::pair<long long, std::pair<int, int> > >::operator()(std::pair<long long, std::pair<int, int> >) const'
/usr/bin/ld: walk.cpp:(.text+0x1fa5): undefined reference to `std::tr1::hash<std::pair<long long, std::pair<int, int> > >::operator()(std::pair<long long, std::pair<int, int> >) const'
/usr/bin/ld: /tmp/ccrLjMWf.o: in function `__gnu_pbds::detail::gp_ht_map<std::pair<int, int>, long long, std::tr1::hash<std::pair<int, int> >, std::equal_to<std::pair<int, int> >, std::allocator<char>, false, __gnu_pbds::direct_mask_range_hashing<unsigned long>, __gnu_pbds::linear_probe_fn<unsigned long>, __gnu_pbds::hash_standard_resize_policy<__gnu_pbds::hash_exponential_size_policy<unsigned long>, __gnu_pbds::hash_load_check_resize_trigger<false, unsigned long>, false, unsigned long> >::resize_imp(unsigned long)':
walk.cpp:(.text._ZN10__gnu_pbds6detail9gp_ht_mapISt4pairIiiExNSt3tr14hashIS3_EESt8equal_toIS3_ESaIcELb0ENS_25direct_mask_range_hashingImEENS_15linear_probe_fnImEENS_27hash_standard_resize_policyINS_28hash_exponential_size_policyImEENS_30hash_load_check_resize_triggerILb0EmEELb0EmEEE10resize_impEm[_ZN10__gnu_pbds6detail9gp_ht_mapISt4pairIiiExNSt3tr14hashIS3_EESt8equal_toIS3_ESaIcELb0ENS_25direct_mask_range_hashingImEENS_15linear_probe_fnImEENS_27hash_standard_resize_policyINS_28hash_exponential_size_policyImEENS_30hash_load_check_resize_triggerILb0EmEELb0EmEEE10resize_impEm]+0x111): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
/usr/bin/ld: /tmp/ccrLjMWf.o: in function `__gnu_pbds::detail::gp_ht_map<std::pair<long long, std::pair<int, int> >, int, std::tr1::hash<std::pair<long long, std::pair<int, int> > >, std::equal_to<std::pair<long long, std::pair<int, int> > >, std::allocator<char>, false, __gnu_pbds::direct_mask_range_hashing<unsigned long>, __gnu_pbds::linear_probe_fn<unsigned long>, __gnu_pbds::hash_standard_resize_policy<__gnu_pbds::hash_exponential_size_policy<unsigned long>, __gnu_pbds::hash_load_check_resize_trigger<false, unsigned long>, false, unsigned long> >::resize_imp(unsigned long)':
walk.cpp:(.text._ZN10__gnu_pbds6detail9gp_ht_mapISt4pairIxS2_IiiEEiNSt3tr14hashIS4_EESt8equal_toIS4_ESaIcELb0ENS_25direct_mask_range_hashingImEENS_15linear_probe_fnImEENS_27hash_standard_resize_policyINS_28hash_exponential_size_policyImEENS_30hash_load_check_resize_triggerILb0EmEELb0EmEEE10resize_impEm[_ZN10__gnu_pbds6detail9gp_ht_mapISt4pairIxS2_IiiEEiNSt3tr14hashIS4_EESt8equal_toIS4_ESaIcELb0ENS_25direct_mask_range_hashingImEENS_15linear_probe_fnImEENS_27hash_standard_resize_policyINS_28hash_exponential_size_policyImEENS_30hash_load_check_resize_triggerILb0EmEELb0EmEEE10resize_impEm]+0x119): undefined reference to `std::tr1::hash<std::pair<long long, std::pair<int, int> > >::operator()(std::pair<long long, std::pair<int, int> >) const'
/usr/bin/ld: /tmp/ccrLjMWf.o: in function `__gnu_pbds::detail::gp_ht_map<std::pair<int, int>, std::vector<std::pair<std::pair<int, int>, int>, std::allocator<std::pair<std::pair<int, int>, int> > >, std::tr1::hash<std::pair<int, int> >, std::equal_to<std::pair<int, int> >, std::allocator<char>, false, __gnu_pbds::direct_mask_range_hashing<unsigned long>, __gnu_pbds::linear_probe_fn<unsigned long>, __gnu_pbds::hash_standard_resize_policy<__gnu_pbds::hash_exponential_size_policy<unsigned long>, __gnu_pbds::hash_load_check_resize_trigger<false, unsigned long>, false, unsigned long> >::resize_imp(unsigned long)':
walk.cpp:(.text._ZN10__gnu_pbds6detail9gp_ht_mapISt4pairIiiESt6vectorIS2_IS3_iESaIS5_EENSt3tr14hashIS3_EESt8equal_toIS3_ESaIcELb0ENS_25direct_mask_range_hashingImEENS_15linear_probe_fnImEENS_27hash_standard_resize_policyINS_28hash_exponential_size_policyImEENS_30hash_load_check_resize_triggerILb0EmEELb0EmEEE10resize_impEm[_ZN10__gnu_pbds6detail9gp_ht_mapISt4pairIiiESt6vectorIS2_IS3_iESaIS5_EENSt3tr14hashIS3_EESt8equal_toIS3_ESaIcELb0ENS_25direct_mask_range_hashingImEENS_15linear_probe_fnImEENS_27hash_standard_resize_policyINS_28hash_exponential_size_policyImEENS_30hash_load_check_resize_triggerILb0EmEELb0EmEEE10resize_impEm]+0x120): undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'
collect2: error: ld returned 1 exit status