oj.uz

Submission #290329

# Submission time Handle Problem Language Result Execution time Memory
290329 2020-09-03T16:01:05 Z MarcoMeijer Sky Walking (IOI19_walk) C++14
43 / 100
 4000 ms 77736 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;

    ll ans = INF;
    map<ii, int> vertexes;
    map<int, vi> horVertex;
    vector<vii> adj;

    auto getVert = [&](int x, int y) {
        if(vertexes.count({x,y})) return vertexes[{x,y}];
        horVertex[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(p,horVertex) sort(all(p.se));
        RE(i,m) {
            if(l[i] == r[i]) continue;
            vi& f = horVertex[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 1 ms 288 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 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 360 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 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Execution timed out 4033 ms 66984 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 14520 KB Output is correct
2 Correct 1819 ms 73108 KB Output is correct
3 Correct 1797 ms 73916 KB Output is correct
4 Correct 1876 ms 75652 KB Output is correct
5 Correct 2172 ms 77592 KB Output is correct
6 Correct 1884 ms 73848 KB Output is correct
7 Correct 735 ms 39544 KB Output is correct
8 Correct 855 ms 48116 KB Output is correct
9 Correct 2752 ms 71284 KB Output is correct
10 Correct 953 ms 46104 KB Output is correct
11 Correct 31 ms 2476 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 14520 KB Output is correct
2 Correct 1819 ms 73108 KB Output is correct
3 Correct 1797 ms 73916 KB Output is correct
4 Correct 1876 ms 75652 KB Output is correct
5 Correct 2172 ms 77592 KB Output is correct
6 Correct 1884 ms 73848 KB Output is correct
7 Correct 735 ms 39544 KB Output is correct
8 Correct 855 ms 48116 KB Output is correct
9 Correct 2752 ms 71284 KB Output is correct
10 Correct 953 ms 46104 KB Output is correct
11 Correct 31 ms 2476 KB Output is correct
12 Correct 1851 ms 73784 KB Output is correct
13 Correct 1805 ms 75200 KB Output is correct
14 Correct 2060 ms 77736 KB Output is correct
15 Correct 1177 ms 57108 KB Output is correct
16 Correct 1262 ms 61528 KB Output is correct
17 Correct 1325 ms 69016 KB Output is correct
18 Correct 1161 ms 57048 KB Output is correct
19 Correct 1281 ms 61340 KB Output is correct
20 Correct 831 ms 38584 KB Output is correct
21 Correct 84 ms 4568 KB Output is correct
22 Correct 1226 ms 60092 KB Output is correct
23 Correct 1120 ms 59016 KB Output is correct
24 Correct 936 ms 47948 KB Output is correct
25 Correct 1018 ms 55472 KB Output is correct
26 Correct 817 ms 43708 KB Output is correct
27 Correct 2538 ms 77688 KB Output is correct
28 Correct 1626 ms 74784 KB Output is correct
29 Correct 1931 ms 73804 KB Output is correct
30 Correct 767 ms 39420 KB Output is correct
31 Correct 1936 ms 71068 KB Output is correct
32 Correct 764 ms 41280 KB Output is correct
33 Correct 790 ms 41076 KB Output is correct
34 Correct 961 ms 47364 KB Output is correct
35 Correct 950 ms 46220 KB Output is correct
36 Correct 743 ms 41036 KB Output is correct
37 Correct 601 ms 37820 KB Output is correct
38 Correct 665 ms 38004 KB Output is correct
39 Correct 1012 ms 52016 KB Output is correct
40 Correct 676 ms 39080 KB Output is correct
41 Correct 628 ms 37464 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 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 360 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 1 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Execution timed out 4033 ms 66984 KB Time limit exceeded
21 Halted 0 ms 0 KB -