oj.uz

Submission #424946

# Submission time Handle Problem Language Result Execution time Memory
424946 2021-06-12T11:55:00 Z TryMax Sky Walking (IOI19_walk) C++17
10 / 100
 979 ms 442212 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 = 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 70752 KB Output is correct
2 Correct 44 ms 70756 KB Output is correct
3 Correct 42 ms 70688 KB Output is correct
4 Correct 41 ms 70672 KB Output is correct
5 Correct 46 ms 70784 KB Output is correct
6 Correct 49 ms 70776 KB Output is correct
7 Correct 50 ms 70752 KB Output is correct
8 Correct 49 ms 70704 KB Output is correct
9 Correct 45 ms 70776 KB Output is correct
10 Correct 44 ms 70744 KB Output is correct
11 Correct 43 ms 70664 KB Output is correct
12 Correct 48 ms 70724 KB Output is correct
13 Correct 54 ms 70660 KB Output is correct
14 Correct 45 ms 70732 KB Output is correct
15 Correct 42 ms 70680 KB Output is correct
16 Correct 42 ms 70696 KB Output is correct
17 Correct 41 ms 70768 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 70752 KB Output is correct
2 Correct 47 ms 70724 KB Output is correct
3 Correct 420 ms 119488 KB Output is correct
4 Incorrect 440 ms 125248 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 80984 KB Output is correct
2 Runtime error 979 ms 442212 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 80984 KB Output is correct
2 Runtime error 979 ms 442212 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 70752 KB Output is correct
2 Correct 44 ms 70756 KB Output is correct
3 Correct 42 ms 70688 KB Output is correct
4 Correct 41 ms 70672 KB Output is correct
5 Correct 46 ms 70784 KB Output is correct
6 Correct 49 ms 70776 KB Output is correct
7 Correct 50 ms 70752 KB Output is correct
8 Correct 49 ms 70704 KB Output is correct
9 Correct 45 ms 70776 KB Output is correct
10 Correct 44 ms 70744 KB Output is correct
11 Correct 43 ms 70664 KB Output is correct
12 Correct 48 ms 70724 KB Output is correct
13 Correct 54 ms 70660 KB Output is correct
14 Correct 45 ms 70732 KB Output is correct
15 Correct 42 ms 70680 KB Output is correct
16 Correct 42 ms 70696 KB Output is correct
17 Correct 41 ms 70768 KB Output is correct
18 Correct 49 ms 70752 KB Output is correct
19 Correct 47 ms 70724 KB Output is correct
20 Correct 420 ms 119488 KB Output is correct
21 Incorrect 440 ms 125248 KB Output isn't correct
22 Halted 0 ms 0 KB -