oj.uz

Submission #411412

# Submission time Handle Problem Language Result Execution time Memory
411412 2021-05-25T08:47:45 Z 조영욱(#7626) Sky Walking (IOI19_walk) C++17
24 / 100
 2447 ms 328992 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

int n,m;
typedef pair<long long,long long> P;
vector<long long> v[100000];
const int sz=131072;
int ssum[100000];
vector<P> adj[1500000];
long long dist[1500000];
bool vis[1500000];

P pmax(P a,P b) {
    return a<b?b:a;
}

P seg[sz*2];

P sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return P(-1,-1);
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return pmax(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}

void update(int i,P val) {
    i+=sz;
    seg[i]=val;
    while (i>1) {
        i/=2;
        seg[i]=pmax(seg[i*2],seg[i*2+1]);
    }
}

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();
    //printf("%d %d\n",n,m);
    for(int i=0;i<n;i++) {
        update(i,P(h[i],i));
    }
    for(int i=0;i<m;i++) {
        vector<P> vec;
        while (1) {
            P got=sum(l[i],r[i]);
            if (got.first<y[i]) {
                for(int ind=0;ind<vec.size();ind++) {
                    update(vec[ind].second,vec[ind]);
                }
                break;
            }
            vec.push_back(got);
            v[got.second].push_back(y[i]);
            update(got.second,P(-1,-1));
        }
    }
    for(int i=0;i<n;i++) {
        v[i].push_back(0);
        sort(v[i].begin(),v[i].end());
        if (i) {
            ssum[i]=ssum[i-1]+v[i-1].size();
        }
        for(int j=1;j<v[i].size();j++) {
            long long dist=v[i][j]-v[i][j-1];
            adj[ssum[i]+j-1].push_back(P(ssum[i]+j,dist));
            adj[ssum[i]+j].push_back(P(ssum[i]+j-1,dist));
            //printf("%d %d %lld\n",ssum[i]+j-1,ssum[i]+j,dist);
        }
    }
    for(int i=0;i<m;i++) {
        vector<P> vec;
        vector<P> vec2;
        while (1) {
            P got=sum(l[i],r[i]);
            if (got.first<y[i]) {
                for(int ind=0;ind<vec.size();ind++) {
                    update(vec[ind].second,vec[ind]);
                }
                break;
            }
            vec.push_back(got);
            update(got.second,P(-1,-1));
            vec2.push_back(P(got.second,y[i]));
        }
        sort(vec2.begin(),vec2.end());
        for(int j=0;j+1<vec2.size();j++) {
            int ind1=ssum[vec2[j].first]+lower_bound(v[vec2[j].first].begin(),v[vec2[j].first].end(),y[i])-v[vec2[j].first].begin();
            int ind2=ssum[vec2[j+1].first]+lower_bound(v[vec2[j+1].first].begin(),v[vec2[j+1].first].end(),y[i])-v[vec2[j+1].first].begin();
            long long dist=x[vec2[j+1].first]-x[vec2[j].first];
            adj[ind1].push_back(P(ind2,dist));
            adj[ind2].push_back(P(ind1,dist));
            //printf("%d %d %lld\n",ind1,ind2,dist);
        }
    }
    int gsz=ssum[n-1]+v[n-1].size();
    for(int i=0;i<gsz;i++) {
        dist[i]=1e16;
    }
    priority_queue<P,vector<P>,greater<P>> pq;
    pq.push(P(0,ssum[s]));
    dist[ssum[s]]=0;
    while (!pq.empty()) {
        int now;
        do {
            now=pq.top().second;
            pq.pop();
        } while (!pq.empty()&&vis[now]);
        if (vis[now]) {
            break;
        }
        vis[now]=true;
        for(int i=0;i<adj[now].size();i++) {
            int nt=adj[now][i].first;
            if (dist[nt]>dist[now]+adj[now][i].second) {
                dist[nt]=dist[now]+adj[now][i].second;
                pq.push(P(dist[nt],nt));
            }
        }
    }
    long long INF=5e15;
	return dist[ssum[g]]>INF?-1:dist[ssum[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:52:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |                 for(int ind=0;ind<vec.size();ind++) {
      |                               ~~~^~~~~~~~~~~
walk.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int j=1;j<v[i].size();j++) {
      |                     ~^~~~~~~~~~~~
walk.cpp:81:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |                 for(int ind=0;ind<vec.size();ind++) {
      |                               ~~~^~~~~~~~~~~
walk.cpp:91:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int j=0;j+1<vec2.size();j++) {
      |                     ~~~^~~~~~~~~~~~
walk.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(int i=0;i<adj[now].size();i++) {
      |                     ~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37836 KB Output is correct
2 Correct 22 ms 37912 KB Output is correct
3 Correct 23 ms 37928 KB Output is correct
4 Correct 22 ms 37844 KB Output is correct
5 Correct 22 ms 37984 KB Output is correct
6 Correct 26 ms 37952 KB Output is correct
7 Correct 23 ms 37904 KB Output is correct
8 Correct 22 ms 37932 KB Output is correct
9 Correct 22 ms 37836 KB Output is correct
10 Correct 23 ms 38024 KB Output is correct
11 Correct 24 ms 37964 KB Output is correct
12 Correct 22 ms 37964 KB Output is correct
13 Correct 22 ms 37904 KB Output is correct
14 Correct 21 ms 37848 KB Output is correct
15 Correct 22 ms 37932 KB Output is correct
16 Correct 22 ms 37836 KB Output is correct
17 Correct 25 ms 38056 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37824 KB Output is correct
2 Correct 23 ms 37892 KB Output is correct
3 Correct 1648 ms 118908 KB Output is correct
4 Correct 1683 ms 128212 KB Output is correct
5 Correct 1254 ms 116028 KB Output is correct
6 Correct 1088 ms 106952 KB Output is correct
7 Correct 1224 ms 116120 KB Output is correct
8 Correct 2204 ms 140456 KB Output is correct
9 Correct 1419 ms 114012 KB Output is correct
10 Correct 2447 ms 161024 KB Output is correct
11 Correct 912 ms 82644 KB Output is correct
12 Correct 564 ms 71376 KB Output is correct
13 Correct 1995 ms 146580 KB Output is correct
14 Correct 540 ms 69700 KB Output is correct
15 Correct 588 ms 71344 KB Output is correct
16 Correct 711 ms 71212 KB Output is correct
17 Correct 549 ms 69836 KB Output is correct
18 Correct 429 ms 72564 KB Output is correct
19 Correct 39 ms 39500 KB Output is correct
20 Correct 251 ms 53984 KB Output is correct
21 Correct 511 ms 68696 KB Output is correct
22 Correct 514 ms 71308 KB Output is correct
23 Correct 740 ms 76632 KB Output is correct
24 Correct 559 ms 70748 KB Output is correct
25 Correct 543 ms 69640 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 51268 KB Output is correct
2 Runtime error 2397 ms 328992 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 228 ms 51268 KB Output is correct
2 Runtime error 2397 ms 328992 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 25 ms 37836 KB Output is correct
2 Correct 22 ms 37912 KB Output is correct
3 Correct 23 ms 37928 KB Output is correct
4 Correct 22 ms 37844 KB Output is correct
5 Correct 22 ms 37984 KB Output is correct
6 Correct 26 ms 37952 KB Output is correct
7 Correct 23 ms 37904 KB Output is correct
8 Correct 22 ms 37932 KB Output is correct
9 Correct 22 ms 37836 KB Output is correct
10 Correct 23 ms 38024 KB Output is correct
11 Correct 24 ms 37964 KB Output is correct
12 Correct 22 ms 37964 KB Output is correct
13 Correct 22 ms 37904 KB Output is correct
14 Correct 21 ms 37848 KB Output is correct
15 Correct 22 ms 37932 KB Output is correct
16 Correct 22 ms 37836 KB Output is correct
17 Correct 25 ms 38056 KB Output is correct
18 Correct 25 ms 37824 KB Output is correct
19 Correct 23 ms 37892 KB Output is correct
20 Correct 1648 ms 118908 KB Output is correct
21 Correct 1683 ms 128212 KB Output is correct
22 Correct 1254 ms 116028 KB Output is correct
23 Correct 1088 ms 106952 KB Output is correct
24 Correct 1224 ms 116120 KB Output is correct
25 Correct 2204 ms 140456 KB Output is correct
26 Correct 1419 ms 114012 KB Output is correct
27 Correct 2447 ms 161024 KB Output is correct
28 Correct 912 ms 82644 KB Output is correct
29 Correct 564 ms 71376 KB Output is correct
30 Correct 1995 ms 146580 KB Output is correct
31 Correct 540 ms 69700 KB Output is correct
32 Correct 588 ms 71344 KB Output is correct
33 Correct 711 ms 71212 KB Output is correct
34 Correct 549 ms 69836 KB Output is correct
35 Correct 429 ms 72564 KB Output is correct
36 Correct 39 ms 39500 KB Output is correct
37 Correct 251 ms 53984 KB Output is correct
38 Correct 511 ms 68696 KB Output is correct
39 Correct 514 ms 71308 KB Output is correct
40 Correct 740 ms 76632 KB Output is correct
41 Correct 559 ms 70748 KB Output is correct
42 Correct 543 ms 69640 KB Output is correct
43 Correct 228 ms 51268 KB Output is correct
44 Runtime error 2397 ms 328992 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -