oj.uz

답안 #424943

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
424943 2021-06-12T11:53:55 Z TryMax Sky Walking (IOI19_walk) C++17
10 / 100
 882 ms 442324 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}), 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

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 70720 KB Output is correct
2 Correct 47 ms 70692 KB Output is correct
3 Correct 48 ms 70736 KB Output is correct
4 Correct 46 ms 70716 KB Output is correct
5 Correct 45 ms 70732 KB Output is correct
6 Correct 47 ms 70804 KB Output is correct
7 Correct 45 ms 70732 KB Output is correct
8 Correct 45 ms 70732 KB Output is correct
9 Correct 51 ms 70716 KB Output is correct
10 Correct 49 ms 70808 KB Output is correct
11 Correct 49 ms 70800 KB Output is correct
12 Correct 48 ms 70780 KB Output is correct
13 Correct 46 ms 70688 KB Output is correct
14 Correct 48 ms 70780 KB Output is correct
15 Correct 48 ms 70800 KB Output is correct
16 Correct 50 ms 70720 KB Output is correct
17 Correct 53 ms 70760 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 70892 KB Output is correct
2 Correct 49 ms 70696 KB Output is correct
3 Correct 442 ms 123584 KB Output is correct
4 Incorrect 471 ms 134036 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 81272 KB Output is correct
2 Runtime error 882 ms 442324 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 81272 KB Output is correct
2 Runtime error 882 ms 442324 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 70720 KB Output is correct
2 Correct 47 ms 70692 KB Output is correct
3 Correct 48 ms 70736 KB Output is correct
4 Correct 46 ms 70716 KB Output is correct
5 Correct 45 ms 70732 KB Output is correct
6 Correct 47 ms 70804 KB Output is correct
7 Correct 45 ms 70732 KB Output is correct
8 Correct 45 ms 70732 KB Output is correct
9 Correct 51 ms 70716 KB Output is correct
10 Correct 49 ms 70808 KB Output is correct
11 Correct 49 ms 70800 KB Output is correct
12 Correct 48 ms 70780 KB Output is correct
13 Correct 46 ms 70688 KB Output is correct
14 Correct 48 ms 70780 KB Output is correct
15 Correct 48 ms 70800 KB Output is correct
16 Correct 50 ms 70720 KB Output is correct
17 Correct 53 ms 70760 KB Output is correct
18 Correct 47 ms 70892 KB Output is correct
19 Correct 49 ms 70696 KB Output is correct
20 Correct 442 ms 123584 KB Output is correct
21 Incorrect 471 ms 134036 KB Output isn't correct
22 Halted 0 ms 0 KB -