oj.uz

Submission #254147

# Submission time Handle Problem Language Result Execution time Memory
254147 2020-07-29T12:02:48 Z khangal Sky Walking (IOI19_walk) C++14
10 / 100
 629 ms 153080 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
#define po pop_back
#define pb push_back
#define mk make_pair
#define lw lower_bound
#define up upper_bound
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MAX 1e18
#define MIN -1e18
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define con continue
#define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,m,ans,mid,mn,mx,T,sum,h1,h2,e[1234567],b[1234567],c[1234567],d[1<<20],k,i,j,l,r,h,a[1234567],w,x,y,z;
bool used[1234567];
vector<int> v[1234567],vec,vv1,vv2;
string s1,s;
long long sz[1234567],par[1234567],tr[3234567],dist[123][123];
ll dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},c1[123][123];
vector<array<ll, 3>> adj[123][123];
const long long inf  = 1e18 + 7;
const int kN = 63;
ll search(ll id, ll val){
    return lw(v[id].begin(), v[id].end(), val) - v[id].begin();
}
long long djikstra(int start1, int start2, int end1, int end2){
    for(int i = 0; i < kN; ++i)
        for(int j = 0; j < kN; ++j)
            dist[i][j] = inf;
    priority_queue<array<long long, 3>, vector<array<long long, 3>>, greater<array<long long, 3>>> pq;
    dist[start1][start2] = 0;
    pq.push({0, start1, start2});
    while(!pq.empty()){
        array<long long, 3> state = pq.top();
        pq.pop();
 
        int u1 = state[1], u2 = state[2];
        if(state[0] != dist[u1][u2])
            continue;
        if(u1 == end1 && u2 == end2)
            break;
 
        for(auto edge: adj[u1][u2]){
            int to1 = edge[0], to2 = edge[1];
            if(dist[to1][to2] > dist[u1][u2] + edge[2]){
                dist[to1][to2] = dist[u1][u2] + edge[2];
                pq.push({dist[to1][to2], to1, to2});
            }
        }
    }
 
    return dist[end1][end2];
}
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
    n = x.size();
    m = y.size();
    sort(x.begin(),x.end());
    for(int i = 0; i < m; ++i){
        for(int j = l[i]; j <= r[i]; ++j){
            if(h[j] >= y[i])
                v[j].push_back(y[i]);
        }
    }
    for(int i = 0; i < n; ++i){
        v[i].push_back(0);
        v[i].push_back(h[i]);
    }
    for(int i = 0; i < n; ++i)
        sort(v[i].begin(), v[i].end());
    for(int i = 0; i < n; ++i){
        vector<int> vec;
        for(int j = 0; j < (int)v[i].size() - 1; ++j){
            if(v[i][j] != v[i][j + 1])
                vec.push_back(v[i][j]);
        }
        if(!v[i].empty())
            vec.push_back(v[i].back());
 
        v[i] = vec;
    }
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < (int)v[i].size() - 1; ++j){
            adj[i][j].push_back({i, j + 1, v[i][j + 1] - v[i][j]});
            adj[i][j + 1].push_back({i, j, v[i][j + 1] - v[i][j]});
        }
    }
    for(int i = 0; i < m; ++i){
        int tmp = -1;
        for(int j = l[i]; j <= r[i]; ++j){
            if(h[j] >= y[i]){
                if(tmp == -1){
                    tmp = j;
                    continue;
                }
 
                int jj = search(j, y[i]), tmpp = search(tmp, y[i]);
                adj[j][jj].push_back({tmp, tmpp, x[j] - x[tmp]});
                adj[tmp][tmpp].push_back({j, jj, x[j] - x[tmp]});
 
                tmp = j;
            }
        }
    }
    ll res = djikstra(s,0,g,0);
    if(res==inf)return -1;
    else return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 29696 KB Output is correct
2 Correct 18 ms 29696 KB Output is correct
3 Correct 17 ms 29696 KB Output is correct
4 Correct 19 ms 29696 KB Output is correct
5 Correct 18 ms 29824 KB Output is correct
6 Correct 16 ms 29824 KB Output is correct
7 Correct 19 ms 29824 KB Output is correct
8 Correct 16 ms 29824 KB Output is correct
9 Correct 16 ms 29824 KB Output is correct
10 Correct 16 ms 29952 KB Output is correct
11 Correct 16 ms 29824 KB Output is correct
12 Correct 16 ms 29824 KB Output is correct
13 Correct 21 ms 29764 KB Output is correct
14 Correct 21 ms 29824 KB Output is correct
15 Correct 22 ms 29824 KB Output is correct
16 Correct 19 ms 29824 KB Output is correct
17 Correct 22 ms 29952 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29696 KB Output is correct
2 Correct 18 ms 29696 KB Output is correct
3 Incorrect 629 ms 153080 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 29696 KB Output is correct
2 Correct 18 ms 29696 KB Output is correct
3 Correct 17 ms 29696 KB Output is correct
4 Correct 19 ms 29696 KB Output is correct
5 Correct 18 ms 29824 KB Output is correct
6 Correct 16 ms 29824 KB Output is correct
7 Correct 19 ms 29824 KB Output is correct
8 Correct 16 ms 29824 KB Output is correct
9 Correct 16 ms 29824 KB Output is correct
10 Correct 16 ms 29952 KB Output is correct
11 Correct 16 ms 29824 KB Output is correct
12 Correct 16 ms 29824 KB Output is correct
13 Correct 21 ms 29764 KB Output is correct
14 Correct 21 ms 29824 KB Output is correct
15 Correct 22 ms 29824 KB Output is correct
16 Correct 19 ms 29824 KB Output is correct
17 Correct 22 ms 29952 KB Output is correct
18 Correct 18 ms 29696 KB Output is correct
19 Correct 18 ms 29696 KB Output is correct
20 Incorrect 629 ms 153080 KB Output isn't correct
21 Halted 0 ms 0 KB -