Submission #426439

#	Time	Username	Problem	Language	Result	Execution time	Memory
426439		mhy908	Sky Walking (IOI19_walk)	C++14	100 / 100	3204 ms	269068 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;

int n, m, toy[200010], s, e;
vector<int> idy;

vector<pii> poss;
int x[100010], h[100010], l[100010], r[100010], y[100010];

vector<int> deln[200010];
vector<pii> line[200010];
vector<int> updm[100010], delm[100010];

vector<int> possx[100010], possy[200010];

map<pii, int> num;
int re;

vector<pil> link[2000010];
LL dist[2000010];
priority_queue<pli, vector<pli>, greater<pli> > pq;

void dbg(){
    for(auto i:idy)printf("%d ", i);
    puts("");
    for(auto i:num)printf("%d -> %d %d\n", i.S, i.F.F-1, toy[i.F.S]);
    while(1){
        int t;
        scanf("%d", &t);
        if(t==0)return;
        for(auto i:link[t])printf("LINK = %d %lld\n", i.F, i.S);
    }
}

LL min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int E){
	n=X.size(); m=Y.size();
	s=min(S, E)+1; e=max(S, E)+1;

	for(auto i:H)idy.eb(i);
	for(auto i:Y)idy.eb(i);
	svec(idy); press(idy);

	for(auto &i:H){
        int tmp=lower_bound(all(idy), i)-idy.begin()+1;
        toy[tmp]=i;
        i=tmp;
	}
	for(auto &i:Y){
        int tmp=lower_bound(all(idy), i)-idy.begin()+1;
        toy[tmp]=i;
        i=tmp;
	}

	for(int i=0; i<n; i++)x[i+1]=X[i];
	for(int i=0; i<n; i++)h[i+1]=H[i];
	for(int i=0; i<m; i++)l[i+1]=L[i]+1;
	for(int i=0; i<m; i++)r[i+1]=R[i]+1;
	for(int i=0; i<m; i++)y[i+1]=Y[i];

	for(int i=1; i<=n; i++)deln[h[i]].eb(i);
	for(int i=1; i<=m; i++){
        line[y[i]].eb(l[i], r[i]);
        updm[l[i]].eb(y[i]);
        delm[r[i]].eb(y[i]);
	}

	set<int> sx;
	for(int i=1; i<=n; i++)sx.insert(i);

	for(int i=1; i<=n+m; i++){
        for(auto j:line[i]){
            poss.eb(j.F, i);
            poss.eb(j.S, i);
            auto it=sx.upper_bound(s);
            if(it!=sx.end()){
                if(j.F<=*it&&*it<=j.S)poss.eb(*it, i);
            }
            if(it!=sx.begin()){
                it--;
                if(j.F<=*it&&*it<=j.S)poss.eb(*it, i);
            }
            it=sx.upper_bound(e);
            if(it!=sx.end()){
                if(j.F<=*it&&*it<=j.S)poss.eb(*it, i);
            }
            if(it!=sx.begin()){
                it--;
                if(j.F<=*it&&*it<=j.S)poss.eb(*it, i);
            }
        }
        for(auto j:deln[i])sx.erase(j);
	}
	svec(poss); press(poss);
    for(auto i:poss)possx[i.F].eb(i.S);

	set<int> sy;
	sy.insert(0);

	for(int i=1; i<=n; i++){
        vector<int> vcvc;
        for(auto j:updm[i]){
            if(sy.find(j)!=sy.end())vcvc.eb(j);
            sy.insert(j);
        }
        for(auto j:possx[i]){
            auto it=sy.lower_bound(j);
            if(it!=sy.begin()){
                it--;
                poss.eb(i, *it);
                it++;
            }
            it++;
            if(it!=sy.end()){
                if(*it<=h[i])poss.eb(i, *it);
            }
            it--;
        }
        for(auto j:delm[i])sy.erase(j);
        for(auto j:vcvc)sy.insert(j);
	}
	for(int i=1; i<=n; i++)poss.eb(i, 0);
	svec(poss); press(poss);

	for(int i=1; i<=n; i++)possx[i].clear();

	for(auto i:poss){
        num[i]=++re;
        possx[i.F].eb(i.S);
        possy[i.S].eb(i.F);
	}

	for(int i=1; i<=n; i++){
        svec(possx[i]);
        for(int j=1; j<possx[i].size(); j++){
            LL d=(LL)toy[possx[i][j]]-(LL)toy[possx[i][j-1]];
            int st=num[mp(i, possx[i][j-1])];
            int fin=num[mp(i, possx[i][j])];
            link[st].eb(fin, d);
            link[fin].eb(st, d);
        }
	}

	for(int i=1; i<=n+m; i++){
        if(possy[i].size()<=1)continue;
        vector<pii> updvc;
        for(auto j:line[i]){
            updvc.eb(j.F, 1);
            updvc.eb(j.S, -1);
        }
        svec(possy[i]);
        svec(updvc);
        int pv=0, sum=0;
        for(int j=0; j<possy[i].size()-1; j++){
            for(; pv<updvc.size(); pv++){
                if(possy[i][j]<updvc[pv].F)break;
                sum+=updvc[pv].S;
            }
            if(!sum)continue;
            LL d=(LL)x[possy[i][j+1]]-(LL)x[possy[i][j]];
            int st=num[mp(possy[i][j], i)];
            int fin=num[mp(possy[i][j+1], i)];
            link[st].eb(fin, d);
            link[fin].eb(st, d);
        }
	}

    //dbg();

	for(int i=1; i<=re; i++)dist[i]=LLINF;
	pq.push(mp(0ll, num[mp(s, 0)]));

	while(pq.size()){
        int nw=pq.top().S; LL d=pq.top().F;
        pq.pop();
        if(dist[nw]<=d)continue;
        dist[nw]=d;
        for(auto i:link[nw])pq.push(mp(d+i.S, i.F));
	}

	/*
    for(auto i:num){
        printf("%d %d -> %lld\n", i.F.F-1, toy[i.F.S], dist[i.S]);
    }
    */
    if(dist[num[mp(e, 0)]]==LLINF)return -1;
	return dist[num[mp(e, 0)]];
}

Compilation message (stderr)

walk.cpp: In function 'LL min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:149:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for(int j=1; j<possx[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~~~
walk.cpp:168:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |         for(int j=0; j<possy[i].size()-1; j++){
      |                      ~^~~~~~~~~~~~~~~~~~
walk.cpp:169:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |             for(; pv<updvc.size(); pv++){
      |                   ~~^~~~~~~~~~~~~
walk.cpp: In function 'void dbg()':
walk.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%d", &t);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 43 / 43