oj.uz

Submission #737333

# Submission time Handle Problem Language Result Execution time Memory
737333 2023-05-07T05:00:55 Z bobthebuilder Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 437712 KB 
#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define lowb(x) (x&(-x))
#define ALL(_x) _x.begin(),_x.end()
#define pii pair<int,int>
#define f first
#define s second
#define SORT_UNIQUE(x) sort(ALL(x)),x.erase(unique(ALL(x)),x.end())
#define ll long long
const ll INF64=4e18;
const int maxn=2e6+5;
vector<pii> gr[maxn];
void add(int a,int b,int w){
	gr[a].pb({b,w}),gr[b].pb({a,w});
}
vector<pii> pts[maxn];
ll dist[maxn];
long long min_distance(std::vector<int> xx, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	int n=sz(xx),m=sz(l);
	vector<pii> v;
	REP(i,n){
		v.pb({h[i],i});
		pts[i].pb({0,i});
	}
	vector<pii> vv;
	sort(ALL(v));
	REP(i,m){
		vv.pb({y[i],i});
	}
	sort(ALL(vv));
	int p=0;
	set<int> ss;
	REP(i,n) ss.insert(i);
	int cur=n;
	for(auto x:vv){
		while(p<n and v[p].f<x.f){
			ss.erase(ss.find(v[p].s));
			++p;
		}
		int a=l[x.s],b=r[x.s];
		auto it=ss.lower_bound(a);
		int pp=-1;
		while(it!=ss.end() and (*it)<=b){
			int z=(*it);
			auto pv=pts[z].back();
			add(pv.s,cur,x.f-pv.f);
			pts[z].pb({x.f,cur});
			if(pp!=-1) add(cur-1,cur,xx[z]-xx[pp]);
			pp=z;
			++cur;
			++it;
		}
	}
	REP(i,cur) dist[i]=INF64;
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({0,s});
	dist[s]=0;
	while(sz(pq)){
		int z=pq.top().s;
		if(pq.top().f>dist[z]){
			pq.pop();
			continue;
		}
		pq.pop();
		for(auto x:gr[z]){
			if(dist[x.f]>dist[z]+x.s){
				dist[x.f]=dist[z]+x.s;
				pq.push({dist[x.f],x.f});
			}
		}
	}
	if(dist[g]==INF64) dist[g]=-1;
	return dist[g];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94172 KB Output is correct
2 Correct 46 ms 94228 KB Output is correct
3 Correct 50 ms 94136 KB Output is correct
4 Correct 46 ms 94208 KB Output is correct
5 Correct 46 ms 94284 KB Output is correct
6 Correct 44 ms 94304 KB Output is correct
7 Correct 51 ms 94220 KB Output is correct
8 Correct 45 ms 94256 KB Output is correct
9 Correct 46 ms 94144 KB Output is correct
10 Correct 45 ms 94256 KB Output is correct
11 Correct 56 ms 94156 KB Output is correct
12 Correct 47 ms 94176 KB Output is correct
13 Correct 54 ms 94220 KB Output is correct
14 Correct 48 ms 94224 KB Output is correct
15 Correct 50 ms 94232 KB Output is correct
16 Correct 46 ms 94168 KB Output is correct
17 Correct 48 ms 94212 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94188 KB Output is correct
2 Correct 45 ms 94140 KB Output is correct
3 Correct 430 ms 147340 KB Output is correct
4 Execution timed out 4053 ms 160616 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 105028 KB Output is correct
2 Runtime error 558 ms 437712 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 118 ms 105028 KB Output is correct
2 Runtime error 558 ms 437712 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 45 ms 94172 KB Output is correct
2 Correct 46 ms 94228 KB Output is correct
3 Correct 50 ms 94136 KB Output is correct
4 Correct 46 ms 94208 KB Output is correct
5 Correct 46 ms 94284 KB Output is correct
6 Correct 44 ms 94304 KB Output is correct
7 Correct 51 ms 94220 KB Output is correct
8 Correct 45 ms 94256 KB Output is correct
9 Correct 46 ms 94144 KB Output is correct
10 Correct 45 ms 94256 KB Output is correct
11 Correct 56 ms 94156 KB Output is correct
12 Correct 47 ms 94176 KB Output is correct
13 Correct 54 ms 94220 KB Output is correct
14 Correct 48 ms 94224 KB Output is correct
15 Correct 50 ms 94232 KB Output is correct
16 Correct 46 ms 94168 KB Output is correct
17 Correct 48 ms 94212 KB Output is correct
18 Correct 46 ms 94188 KB Output is correct
19 Correct 45 ms 94140 KB Output is correct
20 Correct 430 ms 147340 KB Output is correct
21 Execution timed out 4053 ms 160616 KB Time limit exceeded
22 Halted 0 ms 0 KB -