oj.uz

Submission #424942

# Submission time Handle Problem Language Result Execution time Memory
424942 2021-06-12T11:53:14 Z TryMax Sky Walking (IOI19_walk) C++17
10 / 100
 120 ms 28344 KB 
#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 = 1e5 + 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}), pr[v.f] = u;
        mark[u] = 1;
    }
    if(dist[g] == inf)
        return -1;
    else{
        int u = g;
        while(u != s){
//            cout << u << " " << dist[u] << " " << pr[u] << " kek" << endl;
            u = pr[u];
        }
        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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2652 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2656 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 2 ms 2636 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2596 KB Output is correct
3 Runtime error 120 ms 28344 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 20808 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 20808 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2652 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2656 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 2 ms 2636 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 2 ms 2596 KB Output is correct
20 Runtime error 120 ms 28344 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -