oj.uz

Submission #290282

# Submission time Handle Problem Language Result Execution time Memory
290282 2020-09-03T15:18:08 Z MarcoMeijer Sky Walking (IOI19_walk) C++14
15 / 100
 2608 ms 84060 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*5);

    // 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 15604 KB Output is correct
2 Correct 1811 ms 76988 KB Output is correct
3 Correct 1848 ms 78324 KB Output is correct
4 Correct 1819 ms 81812 KB Output is correct
5 Correct 2152 ms 84060 KB Output is correct
6 Correct 1763 ms 80364 KB Output is correct
7 Correct 735 ms 43572 KB Output is correct
8 Correct 820 ms 54600 KB Output is correct
9 Correct 2608 ms 77596 KB Output is correct
10 Correct 893 ms 51692 KB Output is correct
11 Correct 15 ms 1916 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 15604 KB Output is correct
2 Correct 1811 ms 76988 KB Output is correct
3 Correct 1848 ms 78324 KB Output is correct
4 Correct 1819 ms 81812 KB Output is correct
5 Correct 2152 ms 84060 KB Output is correct
6 Correct 1763 ms 80364 KB Output is correct
7 Correct 735 ms 43572 KB Output is correct
8 Correct 820 ms 54600 KB Output is correct
9 Correct 2608 ms 77596 KB Output is correct
10 Correct 893 ms 51692 KB Output is correct
11 Correct 15 ms 1916 KB Output is correct
12 Correct 1808 ms 78372 KB Output is correct
13 Correct 1725 ms 81724 KB Output is correct
14 Correct 1971 ms 83964 KB Output is correct
15 Correct 1091 ms 63340 KB Output is correct
16 Correct 1175 ms 67824 KB Output is correct
17 Correct 1238 ms 75372 KB Output is correct
18 Correct 1108 ms 63080 KB Output is correct
19 Correct 1238 ms 67696 KB Output is correct
20 Correct 798 ms 42476 KB Output is correct
21 Correct 42 ms 4600 KB Output is correct
22 Correct 1128 ms 65500 KB Output is correct
23 Correct 1083 ms 64896 KB Output is correct
24 Correct 861 ms 53784 KB Output is correct
25 Correct 963 ms 61424 KB Output is correct
26 Correct 763 ms 49728 KB Output is correct
27 Correct 2450 ms 83816 KB Output is correct
28 Correct 1529 ms 81260 KB Output is correct
29 Correct 1897 ms 80272 KB Output is correct
30 Correct 688 ms 43696 KB Output is correct
31 Correct 1836 ms 77548 KB Output is correct
32 Correct 711 ms 46416 KB Output is correct
33 Incorrect 738 ms 46844 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 -