oj.uz

Submission #873704

# Submission time Handle Problem Language Result Execution time Memory
873704 2023-11-15T13:27:58 Z andrei_boaca Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 373412 KB 
#include "walk.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("fast-math")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll INF=1e18;
int n;
int ind;
vector<pii> muchii[2000005];
vector<pii> nodes[2000005];
ll dist[2000005];
bool comp(pii a,pii b)
{
    return a.second<b.second;
}
void addnode(int x,int y)
{
    ind++;
    nodes[x].push_back({y,ind});
}
bool use[2000005];
void bfs()
{
    for(int i=1;i<=ind;i++)
        dist[i]=INF;
    dist[1]=0;
    priority_queue<pll,vector<pll>, greater<pll>> pq;
    pq.push({0,1});
    while(!pq.empty())
    {
        int nod=pq.top().second;
        if(nod==2)
            return;
        pq.pop();
        if(use[nod])
            continue;
        use[nod]=1;
        for(auto i:muchii[nod])
            if(dist[i.first]>dist[nod]+i.second)
            {
                dist[i.first]=dist[nod]+i.second;
                pq.push({dist[i.first],i.first});
            }
    }
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g)
{
    n=x.size();
    addnode(s,0);
    addnode(g,0);
    for(int i=0;i<l.size();i++)
    {
        int prv=-1;
        for(int j=l[i];j<=r[i];j++)
            if(y[i]<=h[j])
            {
                addnode(j,y[i]);
                if(prv!=-1)
                {
                    int a=ind-1;
                    int b=ind;
                    muchii[a].push_back({b,x[j]-x[prv]});
                    muchii[b].push_back({a,x[j]-x[prv]});
                }
                prv=j;
            }
    }
    for(int i=0;i<n;i++)
        if(!nodes[i].empty())
        {
            sort(nodes[i].begin(),nodes[i].end());
            for(int j=1;j<nodes[i].size();j++)
            {
                ll d=nodes[i][j].first-nodes[i][j-1].first;
                ll a=nodes[i][j].second;
                ll b=nodes[i][j-1].second;
                muchii[a].push_back({b,d});
                muchii[b].push_back({a,d});
            }
        }
    /*for(int i=1;i<=ind;i++)
        sort(muchii[i].begin(),muchii[i].end(),comp);*/
    bfs();
    if(dist[2]==INF)
        return -1;
    return dist[2];
}

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:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0;i<l.size();i++)
      |                 ~^~~~~~~~~
walk.cpp:77:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             for(int j=1;j<nodes[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 97372 KB Output is correct
2 Correct 21 ms 97372 KB Output is correct
3 Correct 21 ms 97372 KB Output is correct
4 Correct 21 ms 97372 KB Output is correct
5 Correct 22 ms 97368 KB Output is correct
6 Correct 22 ms 97372 KB Output is correct
7 Correct 21 ms 97380 KB Output is correct
8 Correct 21 ms 97372 KB Output is correct
9 Correct 22 ms 97372 KB Output is correct
10 Correct 25 ms 97368 KB Output is correct
11 Correct 21 ms 97372 KB Output is correct
12 Correct 25 ms 97368 KB Output is correct
13 Correct 21 ms 97384 KB Output is correct
14 Correct 24 ms 97364 KB Output is correct
15 Correct 20 ms 97368 KB Output is correct
16 Correct 21 ms 97372 KB Output is correct
17 Correct 22 ms 97264 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 97376 KB Output is correct
2 Correct 21 ms 97376 KB Output is correct
3 Correct 289 ms 151204 KB Output is correct
4 Correct 420 ms 153936 KB Output is correct
5 Correct 292 ms 146440 KB Output is correct
6 Correct 622 ms 139888 KB Output is correct
7 Correct 234 ms 146600 KB Output is correct
8 Correct 384 ms 165304 KB Output is correct
9 Correct 296 ms 147024 KB Output is correct
10 Correct 586 ms 174372 KB Output is correct
11 Correct 210 ms 128464 KB Output is correct
12 Correct 141 ms 115364 KB Output is correct
13 Correct 524 ms 167640 KB Output is correct
14 Correct 2137 ms 115468 KB Output is correct
15 Correct 1137 ms 114772 KB Output is correct
16 Correct 179 ms 116564 KB Output is correct
17 Correct 160 ms 116396 KB Output is correct
18 Execution timed out 4042 ms 104804 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 108116 KB Output is correct
2 Runtime error 316 ms 373412 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 78 ms 108116 KB Output is correct
2 Runtime error 316 ms 373412 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 23 ms 97372 KB Output is correct
2 Correct 21 ms 97372 KB Output is correct
3 Correct 21 ms 97372 KB Output is correct
4 Correct 21 ms 97372 KB Output is correct
5 Correct 22 ms 97368 KB Output is correct
6 Correct 22 ms 97372 KB Output is correct
7 Correct 21 ms 97380 KB Output is correct
8 Correct 21 ms 97372 KB Output is correct
9 Correct 22 ms 97372 KB Output is correct
10 Correct 25 ms 97368 KB Output is correct
11 Correct 21 ms 97372 KB Output is correct
12 Correct 25 ms 97368 KB Output is correct
13 Correct 21 ms 97384 KB Output is correct
14 Correct 24 ms 97364 KB Output is correct
15 Correct 20 ms 97368 KB Output is correct
16 Correct 21 ms 97372 KB Output is correct
17 Correct 22 ms 97264 KB Output is correct
18 Correct 22 ms 97376 KB Output is correct
19 Correct 21 ms 97376 KB Output is correct
20 Correct 289 ms 151204 KB Output is correct
21 Correct 420 ms 153936 KB Output is correct
22 Correct 292 ms 146440 KB Output is correct
23 Correct 622 ms 139888 KB Output is correct
24 Correct 234 ms 146600 KB Output is correct
25 Correct 384 ms 165304 KB Output is correct
26 Correct 296 ms 147024 KB Output is correct
27 Correct 586 ms 174372 KB Output is correct
28 Correct 210 ms 128464 KB Output is correct
29 Correct 141 ms 115364 KB Output is correct
30 Correct 524 ms 167640 KB Output is correct
31 Correct 2137 ms 115468 KB Output is correct
32 Correct 1137 ms 114772 KB Output is correct
33 Correct 179 ms 116564 KB Output is correct
34 Correct 160 ms 116396 KB Output is correct
35 Execution timed out 4042 ms 104804 KB Time limit exceeded
36 Halted 0 ms 0 KB -