Submission #1232313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232313		ksu2009en	Sky Walking (IOI19_walk)	C++20	0 / 100	3595 ms	714868 KiB

walk

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef int ll;

#include "walk.h"

map<pair<ll, ll>, ll> mp;

vector<pair<ll, ll>> d [(ll)(2e6 + 7)];
long long dist [(ll)(2e6 + 7)];
bool used [(ll)(2e6 + 7)];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
    ll n = h.size(), m = y.size();
    
    set<pair<ll, ll>> st;
    
    vector<pair<ll, ll>> walk, build;
    for(int i = 0; i < m; i++)
        walk.push_back({y[i], i});
    
    for(int i = 0; i < n; i++)
        build.push_back({h[i], i});
    
    sort(walk.rbegin(), walk.rend());
    
    sort(build.rbegin(), build.rend());

    ll cur = 0;
    
    vector<vector<ll>> inter(n); // for each building, what points of intersection does it have with any of the walks ?
    for(int i = 0; i < n; i++)
        inter[i].push_back(0);
    
    vector<pair<pair<ll, ll>, pair<ll, ll>>> edges;
    
    for(auto i: walk){
        while(cur < build.size() && build[cur].first >= i.first){
            st.insert({x[build[cur].second], build[cur].second});
            cur++;
        }

        auto u = st.lower_bound(pair<ll, ll> {x[l[i.second]], (ll)(-1e9)});

        vector<ll> coord;
        
        while(u != st.end() && u->first <= x[r[i.second]]){
            inter[u->second].push_back(y[i.second]);

            coord.push_back(u->first);

            u++;
        }

        for(int j = 0; j < (ll)(coord.size()) - 1; j++){
            edges.push_back({{coord[j], y[i.second]}, {coord[j + 1], y[i.second]}});
        }
    }
    
    for(int i = 0; i < n; i++){
        sort(inter[i].begin(), inter[i].end());
        for(int j = 0; j < (ll)inter[i].size() - 1; j++){
            edges.push_back({{x[i], inter[i][j]}, {x[i], inter[i][j + 1]}});
        }
    }
    
    vector<pair<ll, ll>> coord;
    for(auto i: edges){
        coord.push_back(i.first);
        coord.push_back(i.second);
    }
    
    sort(coord.begin(), coord.end());
    coord.resize(unique(coord.begin(), coord.end()) - coord.begin());
    
    for(int i = 0; i < (ll)(coord.size()); i++){
        mp[coord[i]] = i + 1;
    }
    
    if(!mp.count({x[s], 0}) || !mp.count({x[g], 0}))
        return -1;
        
    ll tot = (ll)(coord.size());
        
    for(auto i: edges){
        d[mp[i.first]].push_back({mp[i.second], abs(i.first.first - i.second.first) + abs(i.first.second - i.second.second)});
        d[mp[i.second]].push_back({mp[i.first], abs(i.first.first - i.second.first) + abs(i.first.second - i.second.second)});
    }
        
    priority_queue<pair<ll, long long>, vector<pair<ll, long long>>, greater<pair<ll, long long>>> q;
    
    ll s2 = mp[{x[s], 0}], g2 = mp[{x[g], 0}];
        
    for(int i = 1; i <= tot; i++)
        dist[i] = (long long)(1e18);
    
    dist[s2] = 0;
    
    q.push({0, s2});
    
    while(!q.empty()){
        auto v = q.top();
        q.pop();
        
        if(used[v.second])
            continue;
        
        used[v.second] = true;
                
        for(auto i: d[v.second]){
            if(i.second + v.first < dist[i.first]){
                dist[i.first] = i.second + v.first;
                q.push({dist[i.first], i.first});
            }
        }
    }
    
    if(dist[g2] == (long long)(1e18))
        dist[g2] = -1;
    
    return dist[g2];
}

/*
 0 5 14
 5 7 14
 0 3 5
 10 12 14
 7 10
 5 7
 0 3
 -100
 
 4 2
 1 3
 3 5
 5 2
 6 7
 0 2 1
 1 3 5
 0 3
 
 */

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