oj.uz

Submission #293643

# Submission time Handle Problem Language Result Execution time Memory
293643 2020-09-08T08:55:47 Z Autoratch Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 363128 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<long long,int> 

const int N = 1.5e6 + 1;

int n,m,id;
pair<int,int> val[N];
vector<pair<int,int> > ver[N];
vector<pair<long long,int> > adj[N];
long long dist[N];
bool visited[N];
priority_queue<pii,vector<pii>,greater<pii> > q;

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 = l.size();
    for(int i = 0;i < n;i++)
    {
        ver[i].push_back({0,i});
        val[i] = {i,0};
        id++;
    }
    id++;
    for(int i = 0;i < m;i++)
    {
        vector<int> wo;
        for(int j = l[i];j <= r[i];j++) if(h[j]>=y[i]) wo.push_back(j);
        int pr = -1;
        for(int j : wo) 
        {
            val[++id] = {j,y[i]};
            if(pr!=-1)
            {
                adj[id].push_back({x[j]-x[pr],id-1});
                adj[id-1].push_back({x[j]-x[pr],id});
            }
            pr = j;
            ver[j].push_back({y[i],id});
        }
    }
    for(int i = 0;i < n;i++)
    {
        sort(ver[i].begin(),ver[i].end());
        for(int j = 1;j < ver[i].size();j++)
        {
            adj[ver[i][j-1].second].push_back({ver[i][j].first-ver[i][j-1].first,ver[i][j].second});
            adj[ver[i][j].second].push_back({ver[i][j].first-ver[i][j-1].first,ver[i][j-1].second});
        }
    }
    for(int i = 0;i <= id;i++) dist[i] = LLONG_MAX;
    dist[s] = 0;
    q.push({0,s});
    while(!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if(visited[u]) continue;
        visited[u] = true;
        for(auto [w,v] : adj[u]) if(dist[u]+w<dist[v]) dist[v] = dist[u]+w,q.push({dist[v],v});
    }
    if(dist[g]==LLONG_MAX) dist[g] = -1;
    return dist[g];
}

Compilation message

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:46:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int j = 1;j < ver[i].size();j++)
      |                       ~~^~~~~~~~~~~~~~~
walk.cpp:61:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |         for(auto [w,v] : adj[u]) if(dist[u]+w<dist[v]) dist[v] = dist[u]+w,q.push({dist[v],v});
      |                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 70776 KB Output is correct
2 Correct 49 ms 70776 KB Output is correct
3 Correct 50 ms 70780 KB Output is correct
4 Correct 49 ms 70780 KB Output is correct
5 Correct 48 ms 70904 KB Output is correct
6 Correct 48 ms 70912 KB Output is correct
7 Correct 49 ms 70776 KB Output is correct
8 Correct 48 ms 70776 KB Output is correct
9 Correct 50 ms 70808 KB Output is correct
10 Correct 50 ms 70904 KB Output is correct
11 Correct 49 ms 70776 KB Output is correct
12 Correct 49 ms 70908 KB Output is correct
13 Correct 50 ms 70776 KB Output is correct
14 Correct 50 ms 70904 KB Output is correct
15 Correct 48 ms 70776 KB Output is correct
16 Correct 48 ms 70776 KB Output is correct
17 Correct 48 ms 71160 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 70776 KB Output is correct
2 Correct 48 ms 70776 KB Output is correct
3 Correct 757 ms 152640 KB Output is correct
4 Correct 800 ms 161400 KB Output is correct
5 Correct 587 ms 148640 KB Output is correct
6 Correct 2025 ms 139668 KB Output is correct
7 Correct 546 ms 148752 KB Output is correct
8 Correct 958 ms 176232 KB Output is correct
9 Correct 585 ms 151420 KB Output is correct
10 Correct 1074 ms 198256 KB Output is correct
11 Correct 468 ms 119032 KB Output is correct
12 Correct 321 ms 105720 KB Output is correct
13 Correct 920 ms 184568 KB Output is correct
14 Execution timed out 4067 ms 86504 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 85112 KB Output is correct
2 Runtime error 585 ms 363128 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 85112 KB Output is correct
2 Runtime error 585 ms 363128 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 70776 KB Output is correct
2 Correct 49 ms 70776 KB Output is correct
3 Correct 50 ms 70780 KB Output is correct
4 Correct 49 ms 70780 KB Output is correct
5 Correct 48 ms 70904 KB Output is correct
6 Correct 48 ms 70912 KB Output is correct
7 Correct 49 ms 70776 KB Output is correct
8 Correct 48 ms 70776 KB Output is correct
9 Correct 50 ms 70808 KB Output is correct
10 Correct 50 ms 70904 KB Output is correct
11 Correct 49 ms 70776 KB Output is correct
12 Correct 49 ms 70908 KB Output is correct
13 Correct 50 ms 70776 KB Output is correct
14 Correct 50 ms 70904 KB Output is correct
15 Correct 48 ms 70776 KB Output is correct
16 Correct 48 ms 70776 KB Output is correct
17 Correct 48 ms 71160 KB Output is correct
18 Correct 48 ms 70776 KB Output is correct
19 Correct 48 ms 70776 KB Output is correct
20 Correct 757 ms 152640 KB Output is correct
21 Correct 800 ms 161400 KB Output is correct
22 Correct 587 ms 148640 KB Output is correct
23 Correct 2025 ms 139668 KB Output is correct
24 Correct 546 ms 148752 KB Output is correct
25 Correct 958 ms 176232 KB Output is correct
26 Correct 585 ms 151420 KB Output is correct
27 Correct 1074 ms 198256 KB Output is correct
28 Correct 468 ms 119032 KB Output is correct
29 Correct 321 ms 105720 KB Output is correct
30 Correct 920 ms 184568 KB Output is correct
31 Execution timed out 4067 ms 86504 KB Time limit exceeded
32 Halted 0 ms 0 KB -