Submission #424946

#	Time	Username	Problem	Language	Result	Execution time	Memory
424946		TryMax	Sky Walking (IOI19_walk)	C++17	10 / 100	979 ms	442212 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#ifdef LOCAL
    #include "grader.cpp"
#endif // LOCAL

#define f first
#define s second
#define ll long long
#define pb push_back

using namespace std;

const ll N = 3e6 + 10, inf = 1e18 + 10;

ll dist[N], pr[N];
int mark[N], cnt = 0;
pair<int, int> lasty[N];
vector<pair<int, int>> a[N];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
	int n = x.size();
	int m = y.size();
	bool wass = false, wasg = false;
	set<pair<int, int>> st;
	vector<pair<int, pair<int, int>>> ev;
	for(int i = 0; i < n; ++i)
        ev.pb({x[i], {1, i}});
    for(int i = 0; i < m; ++i){
        ev.pb({x[l[i]], {0, i}});
        ev.pb({x[r[i]], {2, i}});
        lasty[i] = {-1, -1};
    }
    sort(ev.begin(), ev.end());
    for(auto v : ev){
        if(v.s.f == 1){
//            cout << v.s.s << endl;
//            for(auto v1 : st){
//                cout << v1.f << " " << v1.s << endl;
//            }
            pair<int, int> last = {cnt++, 0};
            if(v.s.s == s && !wass){
                s = last.f;
                wass = 1;
//                cout << v.s.s << " " << s << " " << v.f << " " << cnt << endl;
            }
            if(v.s.s == g && !wasg){
//                cout << v.s.s << " " << s << " " << v.f << " " << cnt << endl;
                g = last.f;
                wasg = 1;
            }
            for(auto v1 : st){
                if(v1.f > h[v.s.s])
                    break;
                a[cnt].pb({last.f, v1.f - last.s});
                a[last.f].pb({cnt, v1.f - last.s});
                if(lasty[v1.s].f != -1){
//                    cout << cnt << " " << lasty[v1.f].f << " " << v.f - lasty[v1.f].s << endl;
                    a[cnt].pb({lasty[v1.s].f, v.f - lasty[v1.s].s});
                    a[lasty[v1.s].f].pb({cnt, v.f - lasty[v1.s].s});
                }
                lasty[v1.s] = {cnt, v.f};
                last = {cnt++, v1.f};
//                cout << "lmao" << endl;
            }
        }else if(v.s.f == 0)
            st.insert({y[v.s.s], v.s.s});
        else
            st.erase(st.find({y[v.s.s], v.s.s}));
	}
//	for(int i = 0; i < cnt; ++i){
//        cout << i << endl;
//        for(auto v : a[i])
//            cout << v.f << " " << v.s << endl;
//	}
    for(int i = 0; i < cnt; ++i)
        dist[i] = inf;
    dist[s] = 0;
    priority_queue<pair<int, int>> q;
    q.push({0, s});
    while(!q.empty()){
        int u = q.top().s;
        q.pop();
        if(mark[u])
            continue;
        for(auto v : a[u])
            if(dist[u] + v.s < dist[v.f])
                dist[v.f] = dist[u] + v.s, q.push({-1 * dist[v.f], v.f});
        mark[u] = 1;
    }
    if(dist[g] == inf)
        return -1;
    else
        return dist[g];
}
/*
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5

27

5 3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4

21

3 2
1 4
3 4
5 4
1 3 3
3 5 4
0 2
*/

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