oj.uz

Submission #379362

# Submission time Handle Problem Language Result Execution time Memory
379362 2021-03-18T03:12:40 Z Thistle Sky Walking (IOI19_walk) C++14
0 / 100
 1180 ms 193652 KB 
#include "walk.h"
#include<bits/stdc++.h>
#include<fstream>
using namespace std;

using ll=long long;
using H=pair<ll, ll>;
using vi=vector<ll>;
#define vec vector
#define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),(0),(n))
#define fs first
#define sc second
#define all(a) (a).begin(),(a).end()
#define siz(a) ll((a).size())
#define pb emplace_back

class sptable{
	int n;
	vi lgt;
	vec<vi> dat;
public:
	sptable(vec<int> v){
		n=siz(v);
		lgt.assign(n+1,0);
		for(int i=2;i<=n;i++) lgt[i]=lgt[i>>1]+1;
		dat.assign(lgt[n]+1,vi(n));
		rep(i,n) dat[0][i]=v[i];
		rng(i,0,lgt[n]){
			for(int j=0;j+(1<<(i+1))<=n;j++){
				dat[i+1][j]=max(dat[i][j],dat[i][j+(1<<i)]);
			}
		}
	}
	sptable(){}
	ll get(int l,int r){
		if(r<=l) return -1;
		int k=lgt[r-l];
		return max(dat[k][l],dat[k][r-(1<<k)]);
	}
};

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) {
	int n=siz(x);
	int m=siz(l);
	//x=place
	//h=height
	//l,r,y=road
	//s,g=start,goal

	int num=n;
	vec<vec<H>>pos(n);
	rep(i,n) pos[i].pb(H{0,i});
	vec<vec<H>>e(min(n*m+n,m*10+n));
	sptable spt(h);
	rep(i,m){
		int st=l[i];
		while(st!=r[i]){
			pos[st].pb(H{y[i],num++});
			int ok=n,ng=st+1,mid;
			while(ok-ng>1){
				mid=(ok+ng)/2;
				if(spt.get(st+1,mid)>=y[i]) ok=mid;
				else ng=mid;
			}
			ok--;
			e[num-1].pb(H{num,x[ok]-x[st]});
			e[num].pb(H{num-1,x[ok]-x[st]});
			st=ok;
		}
		pos[st].pb(H{y[i],num++});
	}

	rep(i,n){
		sort(all(pos[i]));
		rep(j,siz(pos[i])-1){
			e[pos[i][j].sc].pb(H{pos[i][j+1].sc,pos[i][j+1].fs-pos[i][j].fs});
			e[pos[i][j+1].sc].pb(H{pos[i][j].sc,pos[i][j+1].fs-pos[i][j].fs});
		}
	}
	priority_queue<H, vec<H>, greater<H>>p;
	vec<ll>a(num,1e17);
	a[s]=0;
	p.push(H{0,s});
	while(!p.empty()){
		H t=p.top();p.pop();
		if(t.fs!=a[t.sc]) continue;
		for(auto g:e[t.sc]){
			if(a[g.fs]>t.fs+g.sc){
				a[g.fs]=t.fs+g.sc;
				p.push(H{a[g.fs],g.fs});
			}
		}
	}
	if(a[g]==1e17) a[g]=-1;
	return a[g];
}

Compilation message

walk.cpp: In constructor 'sptable::sptable(std::vector<int>)':
walk.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
walk.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
walk.cpp:28:3: note: in expansion of macro 'rep'
   28 |   rep(i,n) dat[0][i]=v[i];
      |   ^~~
walk.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
walk.cpp:29:3: note: in expansion of macro 'rng'
   29 |   rng(i,0,lgt[n]){
      |   ^~~
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:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
walk.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
walk.cpp:53:2: note: in expansion of macro 'rep'
   53 |  rep(i,n) pos[i].pb(H{0,i});
      |  ^~~
walk.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
walk.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
walk.cpp:56:2: note: in expansion of macro 'rep'
   56 |  rep(i,m){
      |  ^~~
walk.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
walk.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
walk.cpp:74:2: note: in expansion of macro 'rep'
   74 |  rep(i,n){
      |  ^~~
walk.cpp:10:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
walk.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
walk.cpp:76:3: note: in expansion of macro 'rep'
   76 |   rep(j,siz(pos[i])-1){
      |   ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Runtime error 2 ms 492 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 866 ms 111472 KB Output is correct
4 Correct 1180 ms 139368 KB Output is correct
5 Runtime error 76 ms 21996 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 28396 KB Output is correct
2 Runtime error 408 ms 193652 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 132 ms 28396 KB Output is correct
2 Runtime error 408 ms 193652 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 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Runtime error 2 ms 492 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -