oj.uz

답안 #831631

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
831631 2023-08-20T11:34:28 Z Red_Inside Sky Walking (IOI19_walk) C++17
0 / 100
 1075 ms 444380 KB 
#include <bits/stdc++.h>

using namespace std;
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define ll long long
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//const int maxn=2e5+10;
#define o cout <<"BUG\n";
#define pii pair <int, int>

using namespace std;

const int maxn = 1e5+10;

ll n, m, x[maxn], y[maxn], h[maxn], l[maxn], r[maxn];
vector <ll> dot[maxn], ver[maxn];
vector <pair <ll, ll> > edge[2000100];

long long min_distance(vector<int> X, vector<int> H, 
vector<int> L2, vector<int> R2, vector<int> Y2, int s, int g)
{
	m = L2.size();
	s++, g++;
	forn(1, i, m)
	{
		l[i] = L2[i-1]+1;
		r[i] = R2[i-1]+1;
		y[i] = Y2[i-1];
	}
	n = X.size();
	forn(1, i, n)
	{
		x[i] = X[i-1];
		h[i] = H[i-1];
	}
	forn(1, i, m)
	{
		forn(l[i], j, r[i])
		{
			if(h[j] >= y[i])
				dot[j].pb(y[i]);
		}
	}
	int cnt = 0;
	forn(1, i, n)
	{
		dot[i].pb(0);
		sort(all(dot[i]));
		dot[i].erase(unique(all(dot[i])), dot[i].end());
		ver[i].assign(dot[i].size(), 0);
		FOR(0, j, dot[i].size()) ver[i][j] = ++cnt;
		FOR(1, j, dot[i].size())
		{
			edge[ver[i][j]].pb({ver[i][j-1], dot[i][j]-dot[i][j-1]});
			edge[ver[i][j-1]].pb({ver[i][j], dot[i][j]-dot[i][j-1]});
		}
	}
	forn(1, i, m)
	{
		int last = -1;
		int indx = 0;
		forn(l[i], j, r[i])
		{
			if(h[j] < y[i]) continue;
			int se = lower_bound(all(dot[j]), y[i]) - dot[j].begin();
			int nw = ver[j][se];
			if(last != -1)
			{
				edge[last].pb({nw, x[j]-x[indx]});
				edge[nw].pb({last, x[j]-x[indx]});
			}
			indx = j;
			last = nw;
		}
	}
/*	forn(1, i, n)
	{
		cout << " FOR " << i << endl;
		FOR(0, j, dot[i].size()) cout << dot[i][j] << " " << ver[i][j] << endl;
		cout << endl;
	}*/
//	forn(1, i, cnt)
//		for(auto j : edge[i]) cout << i << " " << j.f << " " << j.s << endl;
	ll inf = 1e18;
	vector <ll> dist(cnt+12);
	forn(1, i, cnt)
	{
		dist[i] = inf;
	}
	int v = lower_bound(all(dot[s]), 0) - dot[s].begin();
	v = ver[s][v];
	dist[v] = 0;
	set <pair <ll, int> > st;
	st.insert({0, v});
	while(st.size())
	{
		int v = st.begin()->s;
		st.erase(st.begin());
		for(auto to : edge[v])
		{
			if(dist[to.f] > dist[v] + to.s)
			{
				st.erase({dist[to.f], to.f});
				dist[to.f] = dist[v]+to.s;
				st.insert({dist[to.f], to.f});
			}
		}
	}
	return dist[ver[g][0]];
}

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:6:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(j, i, n) for(int i = j; i < n; ++i)
......
   58 |   FOR(0, j, dot[i].size()) ver[i][j] = ++cnt;
      |          ~~~~~~~~~~~~~~~~              
walk.cpp:58:3: note: in expansion of macro 'FOR'
   58 |   FOR(0, j, dot[i].size()) ver[i][j] = ++cnt;
      |   ^~~
walk.cpp:6:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(j, i, n) for(int i = j; i < n; ++i)
......
   59 |   FOR(1, j, dot[i].size())
      |          ~~~~~~~~~~~~~~~~              
walk.cpp:59:3: note: in expansion of macro 'FOR'
   59 |   FOR(1, j, dot[i].size())
      |   ^~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 51924 KB Output is correct
2 Correct 26 ms 51944 KB Output is correct
3 Correct 22 ms 51964 KB Output is correct
4 Incorrect 22 ms 51952 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 51964 KB Output is correct
2 Correct 23 ms 51972 KB Output is correct
3 Correct 814 ms 142128 KB Output is correct
4 Correct 734 ms 152984 KB Output is correct
5 Correct 435 ms 139408 KB Output is correct
6 Correct 1075 ms 130048 KB Output is correct
7 Incorrect 426 ms 139572 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 63496 KB Output is correct
2 Runtime error 508 ms 444380 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 63496 KB Output is correct
2 Runtime error 508 ms 444380 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 51924 KB Output is correct
2 Correct 26 ms 51944 KB Output is correct
3 Correct 22 ms 51964 KB Output is correct
4 Incorrect 22 ms 51952 KB Output isn't correct
5 Halted 0 ms 0 KB -