oj.uz

Submission #824557

# Submission time Handle Problem Language Result Execution time Memory
824557 2023-08-14T07:37:32 Z Magikarp4000 Sky Walking (IOI19_walk) C++17
24 / 100
 3121 ms 1048576 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 1e5+5, MAXX = 5e6+10;
int n,m;
vector<pair<int,ll>> v[MAXX];
UM<int,UM<int,int>> mp;
vector<int> row[MAXN], col[MAXN];
vector<PII> in[MAXN], out[MAXN];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = x.size(), m = l.size();
    int cur = 0;
    set<PII> sw;
    FOR(i,0,m) in[l[i]].PB({y[i],i}), out[r[i]+1].PB({y[i],i});
    FOR(i,0,n) {
        FORX(u,out[i]) sw.erase(u);
        FORX(u,in[i]) sw.insert(u);
        for (auto it = sw.begin(); it != sw.end() && (it->F) <= h[i]; it++) {
            int e = it->F, idx = it->S;
            if (!mp[e].count(i)) mp[e][i] = cur++;
            row[idx].PB(i);
            col[i].PB(e);
        }
    }
    FOR(i,0,n) {
        int cn = col[i].size();
        FOR(j,0,cn-1) {
            int a = mp[col[i][j]][i], b = mp[col[i][j+1]][i];
            v[a].PB({b,col[i][j+1]-col[i][j]});
            v[b].PB({a,col[i][j+1]-col[i][j]});
        }
    }
    FOR(i,0,m) {
        int rn = row[i].size();
        FOR(j,0,rn-1) {
            int a = mp[y[i]][row[i][j]], b = mp[y[i]][row[i][j+1]];
            v[a].PB({b,x[row[i][j+1]]-x[row[i][j]]});
            v[b].PB({a,x[row[i][j+1]]-x[row[i][j]]});
        }
    }
    // FOR(i,0,m) {
    //     int prev = y[i] > h[l[i]] ? -1 : l[i];
    //     FOR(j,l[i],r[i]) {
    //         pos[j].PB(y[i]);
    //         if (y[i] > h[j+1]) continue;
            
    //         if (prev != -1) {
    //             if (!mp[y[i]].count(x[j])) mp[y[i]][x[j]] = cur++;
    //             if (!mp[y[i]].count(x[j+1])) mp[y[i]][x[j+1]] = cur++;
    //             int a = mp[y[i]][x[j]], b = mp[y[i]][x[j+1]];
    //             // cout << "y x mp: " << y[i] << " " << x[j] << " " << mp[y[i]][x[j]] << ln;
    //             v[a].PB({b,1LL*(x[j+1]-x[j])});
    //             v[b].PB({a,1LL*(x[j+1]-x[j])});
    //         }
            
    //         prev = j+1;
    //     }
    //     // cout << "y x mp: " << y[i] << " " << x[r[i]] << " " << mp[y[i]][x[r[i]]] << ln;
    //     pos[r[i]].PB(y[i]);
    // }
    // FOR(i,0,n) sort(ALL(pos[i]));
    // FOR(i,0,n) {
    //     int pn = pos[i].size();
    //     FOR(j,0,pn-1) {
    //         if (pos[i][j] == pos[i][j+1]) continue;
    //         if (pos[i][j+1] > h[i]) continue;
    //         int a = mp[pos[i][j]][x[i]], b = mp[pos[i][j+1]][x[i]];
    //         v[a].PB({b,pos[i][j+1]-pos[i][j]});
    //         v[b].PB({a,pos[i][j+1]-pos[i][j]});
    //     }
    // }
    int st = -1, en = -1;
    if (!col[s].empty()) {
        st = cur;
        int a = mp[col[s][0]][s], b = cur++;
        v[a].PB({b,col[s][0]});
        v[b].PB({a,col[s][0]});
    }
    if (!col[g].empty()) {
        en = cur;
        int a = mp[col[g][0]][g], b = cur++;
        v[a].PB({b,col[g][0]});
        v[b].PB({a,col[g][0]});
    }
    // cout << "st en: " << st << " " << en << ln;
    if (st == -1 || en == -1) return -1;
    // FOR(i,0,cur+1) {
    //     cout << i << ": ";
    //     FORX(u,v[i]) cout << u.F << " ";
    //     cout << ln;
    // }
    PQ<pair<ll,int>> pq;
    vector<ll> d(cur+1,LLINF);
    pq.push({0LL,st});
    d[st] = 0LL;
    while (!pq.empty()) {
        int t = pq.top().S;
        pq.pop();
        FORX(u,v[t]) {
            if (d[t]+u.S < d[u.F]) {
                d[u.F] = d[t]+u.S;
                pq.push({-d[u.F],u.F});
            }
        }
    }
    return (d[en] == LLINF ? -1LL : d[en]);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 126984 KB Output is correct
2 Correct 59 ms 127072 KB Output is correct
3 Correct 60 ms 127112 KB Output is correct
4 Correct 61 ms 127096 KB Output is correct
5 Correct 68 ms 127132 KB Output is correct
6 Correct 61 ms 127180 KB Output is correct
7 Correct 61 ms 127088 KB Output is correct
8 Correct 61 ms 127100 KB Output is correct
9 Correct 60 ms 127000 KB Output is correct
10 Correct 60 ms 127224 KB Output is correct
11 Correct 60 ms 127064 KB Output is correct
12 Correct 61 ms 127020 KB Output is correct
13 Correct 60 ms 127000 KB Output is correct
14 Correct 66 ms 127056 KB Output is correct
15 Correct 61 ms 127052 KB Output is correct
16 Correct 61 ms 127052 KB Output is correct
17 Correct 65 ms 127316 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 127032 KB Output is correct
2 Correct 60 ms 127052 KB Output is correct
3 Correct 982 ms 254116 KB Output is correct
4 Correct 861 ms 257480 KB Output is correct
5 Correct 586 ms 235224 KB Output is correct
6 Correct 541 ms 224660 KB Output is correct
7 Correct 594 ms 235612 KB Output is correct
8 Correct 1216 ms 282360 KB Output is correct
9 Correct 689 ms 241996 KB Output is correct
10 Correct 1201 ms 299996 KB Output is correct
11 Correct 545 ms 205256 KB Output is correct
12 Correct 359 ms 185980 KB Output is correct
13 Correct 988 ms 283180 KB Output is correct
14 Correct 359 ms 179104 KB Output is correct
15 Correct 337 ms 170988 KB Output is correct
16 Correct 302 ms 169136 KB Output is correct
17 Correct 303 ms 167312 KB Output is correct
18 Correct 334 ms 192760 KB Output is correct
19 Correct 68 ms 129608 KB Output is correct
20 Correct 184 ms 153392 KB Output is correct
21 Correct 270 ms 166460 KB Output is correct
22 Correct 264 ms 167400 KB Output is correct
23 Correct 376 ms 185156 KB Output is correct
24 Correct 296 ms 167920 KB Output is correct
25 Correct 300 ms 167244 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 144296 KB Output is correct
2 Runtime error 3121 ms 1048576 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 144 ms 144296 KB Output is correct
2 Runtime error 3121 ms 1048576 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 59 ms 126984 KB Output is correct
2 Correct 59 ms 127072 KB Output is correct
3 Correct 60 ms 127112 KB Output is correct
4 Correct 61 ms 127096 KB Output is correct
5 Correct 68 ms 127132 KB Output is correct
6 Correct 61 ms 127180 KB Output is correct
7 Correct 61 ms 127088 KB Output is correct
8 Correct 61 ms 127100 KB Output is correct
9 Correct 60 ms 127000 KB Output is correct
10 Correct 60 ms 127224 KB Output is correct
11 Correct 60 ms 127064 KB Output is correct
12 Correct 61 ms 127020 KB Output is correct
13 Correct 60 ms 127000 KB Output is correct
14 Correct 66 ms 127056 KB Output is correct
15 Correct 61 ms 127052 KB Output is correct
16 Correct 61 ms 127052 KB Output is correct
17 Correct 65 ms 127316 KB Output is correct
18 Correct 59 ms 127032 KB Output is correct
19 Correct 60 ms 127052 KB Output is correct
20 Correct 982 ms 254116 KB Output is correct
21 Correct 861 ms 257480 KB Output is correct
22 Correct 586 ms 235224 KB Output is correct
23 Correct 541 ms 224660 KB Output is correct
24 Correct 594 ms 235612 KB Output is correct
25 Correct 1216 ms 282360 KB Output is correct
26 Correct 689 ms 241996 KB Output is correct
27 Correct 1201 ms 299996 KB Output is correct
28 Correct 545 ms 205256 KB Output is correct
29 Correct 359 ms 185980 KB Output is correct
30 Correct 988 ms 283180 KB Output is correct
31 Correct 359 ms 179104 KB Output is correct
32 Correct 337 ms 170988 KB Output is correct
33 Correct 302 ms 169136 KB Output is correct
34 Correct 303 ms 167312 KB Output is correct
35 Correct 334 ms 192760 KB Output is correct
36 Correct 68 ms 129608 KB Output is correct
37 Correct 184 ms 153392 KB Output is correct
38 Correct 270 ms 166460 KB Output is correct
39 Correct 264 ms 167400 KB Output is correct
40 Correct 376 ms 185156 KB Output is correct
41 Correct 296 ms 167920 KB Output is correct
42 Correct 300 ms 167244 KB Output is correct
43 Correct 144 ms 144296 KB Output is correct
44 Runtime error 3121 ms 1048576 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -