oj.uz

Submission #290334

# Submission time Handle Problem Language Result Execution time Memory
290334 2020-09-03T16:05:42 Z MarcoMeijer Sky Walking (IOI19_walk) C++14
43 / 100
 4000 ms 76876 KB 
#include <bits/stdc++.h>
#include "walk.h"
using namespace std;

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a:b)
#define INF 1e18
#define pb push_back
#define fi first
#define se second
#define sz size()
#define all(a) a.begin(), a.end()

ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
    int n=x.sz, m=l.sz, N=0;

    // change graph
    RE(j,2) {
        int x = j ? s : g;
        vi nl, nr, ny;

        priority_queue<iii> pq;

        RE(i,n) pq.push({h[i],2,i});

        RE(i,m) {
            if(l[i] < x && x < r[i]) {
                pq.push({y[i],1,i});
            } else {
                nl.pb(l[i]);
                nr.pb(r[i]);
                ny.pb(y[i]);
            }
        }
        int mostL = -1e9, mostR = 1e9;

        while(!pq.empty()) {
            iii p = pq.top(); pq.pop();
            int y, t, i;
            tie(y,t,i) = p;
            if(t == 2) {
                if(i <= x)
                    mostL = max(mostL, i);
                if(i >= x)
                    mostR = min(mostR, i);
            } else if(t == 1) {
                if(mostL != l[i] ) nl.pb(l[i]) , nr.pb(mostL), ny.pb(y);
                if(mostL != mostR) nl.pb(mostL), nr.pb(mostR), ny.pb(y);
                if(r[i]  != mostR) nl.pb(mostR), nr.pb(r[i]) , ny.pb(y);
            }
        }

        l=nl; r=nr; y=ny;
        m = l.sz;
    }

    l.pb(s); r.pb(s); y.pb(0);
    l.pb(g); r.pb(g); y.pb(0);
    m = l.sz;

    // coördinate compression
    map<int,int> compY; int difY=0;
    {
        set<int> st;
        RE(i,m) st.insert(y[i]);
        FOR(y,st) compY[y]=difY++;
    }

    ll ans = INF;
    map<ii, int> vertexes;
    vector<vi> horVertex; horVertex.resize(difY);
    vector<vii> adj;

    auto getVert = [&](int x, int y) {
        if(vertexes.count({x,y})) return vertexes[{x,y}];
        horVertex[compY[y]].pb(x);
        return vertexes[{x,y}] = N++;
    };
    auto connect = [&](ii a, ii b) {
        int u = getVert(a.fi, a.se);
        int v = getVert(b.fi, b.se);
        int d = abs(a.fi-b.fi)+abs(a.se-b.se);
        adj[u].pb({v,d});
        adj[v].pb({u,d});
    };

    adj.resize(m*4);

    // create vertexes, and vertical edges
    {
        priority_queue<iii> pq;
        multiset<int> st;
        RE(i,m) pq.push({r[i],2,i});
        RE(i,m) pq.push({l[i],1,i});
        RE(i,m) pq.push({r[i],1,i});
        RE(i,m) pq.push({l[i],0,i});
        
        while(!pq.empty()) {
            iii p = pq.top(); pq.pop();
            int cx, t, i;
            tie(cx,t,i) = p;
            if(t == 2) {
                // right
                st.insert(y[i]);
            } else if(t == 1) {
                // connect
                getVert(x[cx], y[i]);
                auto it = st.lower_bound(y[i]);
                if(it != st.begin())
                    --it, connect({x[cx],y[i]}, {x[cx],*it});
            } else {
                // left
                st.erase(st.find(y[i]));
            }
        }
    }

    // create horizontal edges
    {
        FOR(f,horVertex) sort(all(f));
        RE(i,m) {
            if(l[i] == r[i]) continue;
            vi& f = horVertex[compY[y[i]]];
            auto it=lower_bound(all(f), x[l[i]]);
            auto ed=upper_bound(all(f), x[r[i]]);
            while(1) {
                auto prev = it++;
                if(it == ed) break;
                connect({*prev, y[i]}, {*it, y[i]});
            }
        }
    }

    // dijkstra
    {
        vll dist; dist.assign(N, INF);
        priority_queue<lll> pq;
        dist[getVert(x[s],0)] = 0; pq.push({getVert(x[s],0), 0});
        while(!pq.empty()) {
            lll p = pq.top(); pq.pop();
            int u=p.fi; ll d=p.se;
            if(dist[u] != d) continue;
            FOR(p,adj[u]) {
                int v = p.fi;
                ll add = p.se;
                if(d+add < dist[v]) {
                    dist[v] = d+add;
                    pq.push({v,dist[v]});
                }
            }
        }
        ans = dist[getVert(x[g],0)];
    }

    if(ans == INF) ans = -1;
    return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Execution timed out 4104 ms 65344 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 14520 KB Output is correct
2 Correct 1872 ms 71704 KB Output is correct
3 Correct 1898 ms 73056 KB Output is correct
4 Correct 1937 ms 74556 KB Output is correct
5 Correct 2424 ms 76868 KB Output is correct
6 Correct 2020 ms 72444 KB Output is correct
7 Correct 782 ms 38908 KB Output is correct
8 Correct 965 ms 47380 KB Output is correct
9 Correct 2886 ms 69468 KB Output is correct
10 Correct 998 ms 45600 KB Output is correct
11 Correct 31 ms 2468 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 14520 KB Output is correct
2 Correct 1872 ms 71704 KB Output is correct
3 Correct 1898 ms 73056 KB Output is correct
4 Correct 1937 ms 74556 KB Output is correct
5 Correct 2424 ms 76868 KB Output is correct
6 Correct 2020 ms 72444 KB Output is correct
7 Correct 782 ms 38908 KB Output is correct
8 Correct 965 ms 47380 KB Output is correct
9 Correct 2886 ms 69468 KB Output is correct
10 Correct 998 ms 45600 KB Output is correct
11 Correct 31 ms 2468 KB Output is correct
12 Correct 1879 ms 72864 KB Output is correct
13 Correct 1840 ms 74364 KB Output is correct
14 Correct 2092 ms 76828 KB Output is correct
15 Correct 1159 ms 56604 KB Output is correct
16 Correct 1272 ms 61188 KB Output is correct
17 Correct 1291 ms 68764 KB Output is correct
18 Correct 1199 ms 56728 KB Output is correct
19 Correct 1295 ms 60856 KB Output is correct
20 Correct 821 ms 37948 KB Output is correct
21 Correct 80 ms 4568 KB Output is correct
22 Correct 1237 ms 59456 KB Output is correct
23 Correct 1126 ms 58252 KB Output is correct
24 Correct 902 ms 47128 KB Output is correct
25 Correct 1029 ms 54664 KB Output is correct
26 Correct 809 ms 43080 KB Output is correct
27 Correct 2599 ms 76876 KB Output is correct
28 Correct 1608 ms 73928 KB Output is correct
29 Correct 1944 ms 72728 KB Output is correct
30 Correct 741 ms 39056 KB Output is correct
31 Correct 1947 ms 69660 KB Output is correct
32 Correct 782 ms 41336 KB Output is correct
33 Correct 799 ms 40828 KB Output is correct
34 Correct 1002 ms 46748 KB Output is correct
35 Correct 970 ms 45588 KB Output is correct
36 Correct 725 ms 40784 KB Output is correct
37 Correct 598 ms 37564 KB Output is correct
38 Correct 655 ms 37880 KB Output is correct
39 Correct 1038 ms 51612 KB Output is correct
40 Correct 662 ms 38916 KB Output is correct
41 Correct 637 ms 37752 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Execution timed out 4104 ms 65344 KB Time limit exceeded
21 Halted 0 ms 0 KB -