oj.uz

Submission #874245

# Submission time Handle Problem Language Result Execution time Memory
874245 2023-11-16T14:25:18 Z andrei_boaca Sky Walking (IOI19_walk) C++17
43 / 100
 263 ms 69268 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,m;
int ind;
vector<pii> muchii[1000005];
vector<pii> nodes[1000005];
vector<int> where[100005];
int arb[4*100005],toprop[4*100005];
ll dp[100005];
struct skywalk
{
    ll l,r,h,ind;
} v[100005];
ll dist[1000005];
bool comp(pii a,pii b)
{
    return a.second<b.second;
}
bool cresc(skywalk a, skywalk b)
{
    if(a.h!=b.h)
        return a.h<b.h;
    return a.l>b.l;
}
bool byr(skywalk a, skywalk b)
{
    return a.r<b.r;
}
bool descresc(skywalk a, skywalk b)
{
    if(a.h!=b.h)
        return a.h>b.h;
    return a.l>b.l;
}
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});
            }
    }
}
void prop(int nod)
{
    int val=toprop[nod];
    arb[nod*2]=val;
    arb[nod*2+1]=val;
    toprop[nod*2]=val;
    toprop[nod*2+1]=val;
}
void build(int nod,int st,int dr)
{
    arb[nod]=-1;
    toprop[nod]=-1;
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
}
void update(int nod,int st,int dr,int a,int b,int val)
{
    if(toprop[nod]!=-1&&st!=dr)
        prop(nod);
    toprop[nod]=-1;
    if(st>=a&&dr<=b)
    {
        arb[nod]=val;
        toprop[nod]=val;
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        update(nod*2,st,mij,a,b,val);
    if(b>mij)
        update(nod*2+1,mij+1,dr,a,b,val);
}
int query(int nod,int st,int dr,int poz)
{
    if(toprop[nod]!=-1&&st!=dr)
        prop(nod);
    toprop[nod]=-1;
    if(st==dr)
        return arb[nod];
    int mij=(st+dr)/2;
    if(poz<=mij)
        return query(nod*2,st,mij,poz);
    else
        return query(nod*2+1,mij+1,dr,poz);
}
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();
    m=l.size();
    if(x.size()<=50&&l.size()<=50)
    {
        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});
                }
            }
        bfs();
        if(dist[2]==INF)
            return -1;
        return dist[2];
    }
    for(int i=0;i<m;i++)
        v[i]={l[i],r[i],y[i],i};
    sort(v,v+m,cresc);
    build(1,0,n-1);
    for(int i=0;i<m;i++)
    {
        int rgt=v[i].r;
        int val=query(1,0,n-1,rgt);
        if(val!=-1)
            where[v[i].ind].push_back(val);
        update(1,0,n-1,v[i].l,v[i].r,v[i].ind);
    }
    sort(v,v+m,descresc);
    build(1,0,n-1);
    for(int i=0;i<m;i++)
    {
        int rgt=v[i].r;
        int val=query(1,0,n-1,rgt);
        if(val!=-1)
            where[v[i].ind].push_back(val);
        update(1,0,n-1,v[i].l,v[i].r,v[i].ind);
    }
    ll ans=INF;
    queue<int> coada;
    for(int i=0;i<m;i++)
    {
        dp[i]=INF;
        if(l[i]==0)
        {
            dp[i]=y[i];
            coada.push(i);
        }
    }
    while(!coada.empty())
    {
        int nod=coada.front();
        coada.pop();
        if(r[nod]==n-1)
            ans=min(ans,dp[nod]+y[nod]+x[n-1]-x[0]);
        for(int i:where[nod])
            if(dp[i]>dp[nod]+abs(y[i]-y[nod]))
            {
                dp[i]=dp[nod]+abs(y[i]-y[nod]);
                coada.push(i);
            }
        }
    if(ans==INF)
        return -1;
    return ans;
}

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 52312 KB Output is correct
2 Correct 11 ms 52060 KB Output is correct
3 Correct 11 ms 51896 KB Output is correct
4 Correct 11 ms 51804 KB Output is correct
5 Correct 11 ms 51916 KB Output is correct
6 Correct 11 ms 51912 KB Output is correct
7 Correct 11 ms 52060 KB Output is correct
8 Correct 11 ms 52060 KB Output is correct
9 Correct 11 ms 52060 KB Output is correct
10 Correct 11 ms 51908 KB Output is correct
11 Correct 13 ms 52060 KB Output is correct
12 Correct 11 ms 51888 KB Output is correct
13 Correct 11 ms 52060 KB Output is correct
14 Correct 11 ms 52036 KB Output is correct
15 Correct 11 ms 51932 KB Output is correct
16 Correct 11 ms 52060 KB Output is correct
17 Correct 11 ms 52060 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 51804 KB Output is correct
2 Correct 11 ms 52028 KB Output is correct
3 Incorrect 263 ms 63864 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 61020 KB Output is correct
2 Correct 99 ms 63692 KB Output is correct
3 Correct 123 ms 65700 KB Output is correct
4 Correct 152 ms 69196 KB Output is correct
5 Correct 167 ms 69128 KB Output is correct
6 Correct 149 ms 69228 KB Output is correct
7 Correct 81 ms 65492 KB Output is correct
8 Correct 125 ms 69200 KB Output is correct
9 Correct 147 ms 69192 KB Output is correct
10 Correct 121 ms 68416 KB Output is correct
11 Correct 20 ms 57692 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 61020 KB Output is correct
2 Correct 99 ms 63692 KB Output is correct
3 Correct 123 ms 65700 KB Output is correct
4 Correct 152 ms 69196 KB Output is correct
5 Correct 167 ms 69128 KB Output is correct
6 Correct 149 ms 69228 KB Output is correct
7 Correct 81 ms 65492 KB Output is correct
8 Correct 125 ms 69200 KB Output is correct
9 Correct 147 ms 69192 KB Output is correct
10 Correct 121 ms 68416 KB Output is correct
11 Correct 20 ms 57692 KB Output is correct
12 Correct 123 ms 65840 KB Output is correct
13 Correct 157 ms 69196 KB Output is correct
14 Correct 156 ms 69204 KB Output is correct
15 Correct 134 ms 69104 KB Output is correct
16 Correct 130 ms 69208 KB Output is correct
17 Correct 131 ms 69216 KB Output is correct
18 Correct 133 ms 68880 KB Output is correct
19 Correct 137 ms 69268 KB Output is correct
20 Correct 92 ms 65620 KB Output is correct
21 Correct 30 ms 59740 KB Output is correct
22 Correct 120 ms 67932 KB Output is correct
23 Correct 122 ms 68196 KB Output is correct
24 Correct 116 ms 68432 KB Output is correct
25 Correct 113 ms 67964 KB Output is correct
26 Correct 117 ms 68264 KB Output is correct
27 Correct 156 ms 69220 KB Output is correct
28 Correct 141 ms 69212 KB Output is correct
29 Correct 156 ms 69232 KB Output is correct
30 Correct 85 ms 65368 KB Output is correct
31 Correct 152 ms 69084 KB Output is correct
32 Correct 112 ms 68176 KB Output is correct
33 Correct 108 ms 68304 KB Output is correct
34 Correct 108 ms 68172 KB Output is correct
35 Correct 119 ms 68296 KB Output is correct
36 Correct 151 ms 67920 KB Output is correct
37 Correct 108 ms 67412 KB Output is correct
38 Correct 110 ms 68300 KB Output is correct
39 Correct 105 ms 68176 KB Output is correct
40 Correct 118 ms 67924 KB Output is correct
41 Correct 116 ms 67412 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 52312 KB Output is correct
2 Correct 11 ms 52060 KB Output is correct
3 Correct 11 ms 51896 KB Output is correct
4 Correct 11 ms 51804 KB Output is correct
5 Correct 11 ms 51916 KB Output is correct
6 Correct 11 ms 51912 KB Output is correct
7 Correct 11 ms 52060 KB Output is correct
8 Correct 11 ms 52060 KB Output is correct
9 Correct 11 ms 52060 KB Output is correct
10 Correct 11 ms 51908 KB Output is correct
11 Correct 13 ms 52060 KB Output is correct
12 Correct 11 ms 51888 KB Output is correct
13 Correct 11 ms 52060 KB Output is correct
14 Correct 11 ms 52036 KB Output is correct
15 Correct 11 ms 51932 KB Output is correct
16 Correct 11 ms 52060 KB Output is correct
17 Correct 11 ms 52060 KB Output is correct
18 Correct 11 ms 51804 KB Output is correct
19 Correct 11 ms 52028 KB Output is correct
20 Incorrect 263 ms 63864 KB Output isn't correct
21 Halted 0 ms 0 KB -