oj.uz

Submission #290291

# Submission time Handle Problem Language Result Execution time Memory
290291 2020-09-03T15:25:47 Z MarcoMeijer Sky Walking (IOI19_walk) C++14
15 / 100
 2845 ms 84668 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) {
    l.pb(s); r.pb(s); y.pb(0);
    l.pb(g); r.pb(g); y.pb(0);
    int n=x.sz, m=l.sz, N=0;

    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*7);

    // create vertexes, and vertical edges
    {
        priority_queue<iii> pq;
        set<int> st;
        RE(i,m) pq.push({r[i],2,i});
        RE(i,m) pq.push({r[i],1,i});
        RE(i,m) pq.push({l[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(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(it != ed) {
                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;
}

Compilation message

walk.cpp: In function 'll min_distance(vi, vi, vi, vi, vi, int, int)':
walk.cpp:31:9: warning: unused variable 'n' [-Wunused-variable]
   31 |     int n=x.sz, m=l.sz, N=0;
      |         ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 17188 KB Output is correct
2 Correct 1873 ms 80076 KB Output is correct
3 Correct 1865 ms 81132 KB Output is correct
4 Correct 1915 ms 82664 KB Output is correct
5 Correct 2294 ms 84560 KB Output is correct
6 Correct 2033 ms 80884 KB Output is correct
7 Correct 771 ms 43000 KB Output is correct
8 Correct 871 ms 55120 KB Output is correct
9 Correct 2845 ms 78060 KB Output is correct
10 Correct 978 ms 52932 KB Output is correct
11 Correct 15 ms 1152 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 17188 KB Output is correct
2 Correct 1873 ms 80076 KB Output is correct
3 Correct 1865 ms 81132 KB Output is correct
4 Correct 1915 ms 82664 KB Output is correct
5 Correct 2294 ms 84560 KB Output is correct
6 Correct 2033 ms 80884 KB Output is correct
7 Correct 771 ms 43000 KB Output is correct
8 Correct 871 ms 55120 KB Output is correct
9 Correct 2845 ms 78060 KB Output is correct
10 Correct 978 ms 52932 KB Output is correct
11 Correct 15 ms 1152 KB Output is correct
12 Correct 1986 ms 80752 KB Output is correct
13 Correct 1883 ms 82404 KB Output is correct
14 Correct 2145 ms 84652 KB Output is correct
15 Correct 1171 ms 64032 KB Output is correct
16 Correct 1309 ms 68376 KB Output is correct
17 Correct 1306 ms 76108 KB Output is correct
18 Correct 1134 ms 64104 KB Output is correct
19 Correct 1274 ms 68464 KB Output is correct
20 Correct 870 ms 41940 KB Output is correct
21 Correct 42 ms 2680 KB Output is correct
22 Correct 1320 ms 65828 KB Output is correct
23 Correct 1228 ms 65208 KB Output is correct
24 Correct 1000 ms 53968 KB Output is correct
25 Correct 1117 ms 61328 KB Output is correct
26 Correct 799 ms 50112 KB Output is correct
27 Correct 2529 ms 84668 KB Output is correct
28 Correct 1567 ms 82016 KB Output is correct
29 Correct 1935 ms 80748 KB Output is correct
30 Correct 791 ms 43056 KB Output is correct
31 Correct 1959 ms 78396 KB Output is correct
32 Correct 761 ms 48084 KB Output is correct
33 Incorrect 768 ms 48076 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -