oj.uz

Submission #873683

# Submission time Handle Problem Language Result Execution time Memory
873683 2023-11-15T13:11:18 Z andrei_boaca Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 280548 KB 
#include "walk.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
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;
unordered_map<int,int> f[100005];
vector<pii> muchii[1000005];
vector<pii> nodes[1000005];
ll dist[1000005];
void addnode(int x,int y)
{
    if(f[x][y]!=0)
        return;
    ind++;
    f[x][y]=ind;
    nodes[x].push_back({y,ind});
}
bool use[1000005];
void bfs()
{
    for(int i=1;i<=ind;i++)
        dist[i]=INF;
    dist[1]=0;
    queue<pll> pq;
    pq.push({0,1});
    while(!pq.empty())
    {
        int nod=pq.front().second;
        pq.pop();
        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=f[prv][y[i]];
                    int b=f[j][y[i]];
                    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});
            }
        }
    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:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0;i<l.size();i++)
      |                 ~^~~~~~~~~
walk.cpp:73: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]
   73 |             for(int j=1;j<nodes[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 55132 KB Output is correct
2 Correct 12 ms 55132 KB Output is correct
3 Correct 12 ms 55132 KB Output is correct
4 Correct 12 ms 55372 KB Output is correct
5 Correct 12 ms 55388 KB Output is correct
6 Correct 12 ms 55388 KB Output is correct
7 Correct 12 ms 55388 KB Output is correct
8 Correct 12 ms 55388 KB Output is correct
9 Correct 12 ms 55268 KB Output is correct
10 Correct 12 ms 55388 KB Output is correct
11 Correct 12 ms 55324 KB Output is correct
12 Correct 12 ms 55388 KB Output is correct
13 Correct 12 ms 55308 KB Output is correct
14 Correct 12 ms 55388 KB Output is correct
15 Correct 12 ms 55132 KB Output is correct
16 Correct 12 ms 55132 KB Output is correct
17 Correct 14 ms 55388 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 55128 KB Output is correct
2 Correct 13 ms 55132 KB Output is correct
3 Execution timed out 4062 ms 154664 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 64220 KB Output is correct
2 Runtime error 452 ms 280548 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 48 ms 64220 KB Output is correct
2 Runtime error 452 ms 280548 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 12 ms 55132 KB Output is correct
2 Correct 12 ms 55132 KB Output is correct
3 Correct 12 ms 55132 KB Output is correct
4 Correct 12 ms 55372 KB Output is correct
5 Correct 12 ms 55388 KB Output is correct
6 Correct 12 ms 55388 KB Output is correct
7 Correct 12 ms 55388 KB Output is correct
8 Correct 12 ms 55388 KB Output is correct
9 Correct 12 ms 55268 KB Output is correct
10 Correct 12 ms 55388 KB Output is correct
11 Correct 12 ms 55324 KB Output is correct
12 Correct 12 ms 55388 KB Output is correct
13 Correct 12 ms 55308 KB Output is correct
14 Correct 12 ms 55388 KB Output is correct
15 Correct 12 ms 55132 KB Output is correct
16 Correct 12 ms 55132 KB Output is correct
17 Correct 14 ms 55388 KB Output is correct
18 Correct 12 ms 55128 KB Output is correct
19 Correct 13 ms 55132 KB Output is correct
20 Execution timed out 4062 ms 154664 KB Time limit exceeded
21 Halted 0 ms 0 KB -