oj.uz

Submission #290328

# Submission time Handle Problem Language Result Execution time Memory
290328 2020-09-03T16:00:32 Z MarcoMeijer Sky Walking (IOI19_walk) C++14
0 / 100
 4000 ms 73708 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);
        if(adj.size() < N) adj.resize(N+1);
        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*2);

    // 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;
}

Compilation message

walk.cpp: In lambda function:
walk.cpp:83:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |         if(adj.size() < N) adj.resize(N+1);
      |            ~~~~~~~~~~~^~~

Subtask #1
0 / 10.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 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 Runtime error 1 ms 512 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

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 4083 ms 64268 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 12344 KB Output is correct
2 Execution timed out 4075 ms 73708 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 12344 KB Output is correct
2 Execution timed out 4075 ms 73708 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.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 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 Runtime error 1 ms 512 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -