oj.uz

답안 #416774

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
416774 2021-06-02T22:13:00 Z peuch Sky Walking (IOI19_walk) C++17
0 / 100
 941 ms 52760 KB 
#include "walk.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;
const long long INF = 1e18;

map<pair<int, int>, int> node;
vector<long long> dist;
vector<bool> marc;
vector<vector<int> > ar, wg;

struct event{
	int l, r, h;
	event(int _l = 0, int _r = 0, int _h = 0){
		l = _l, r = _r, h = _h;
	}
	bool operator < (event x) const {
		if(h == x.h) return r - l < x.r - x.l;
		return h > x.h;	
	}
};

vector<event> line;
vector<int> last;

void dijkstra(int ini);

int create(int x, int y){
	if(node[make_pair(x, y)] != 0) return node[make_pair(x, y)];
	node[make_pair(x, y)] = ar.size();
	ar.push_back(vector<int>(0));
	wg.push_back(vector<int>(0));
	dist.push_back(INF);
	marc.push_back(0);
	if(last[x] != 0) {
		ar[node[make_pair(x, y)]].push_back(node[make_pair(x, last[x])]);
		ar[node[make_pair(x, last[x])]].push_back(node[make_pair(x, y)]);
		wg[node[make_pair(x, y)]].push_back(abs(y - last[x]));
		wg[node[make_pair(x, last[x])]].push_back(abs(y - last[x]));
	}
	last[x] = y;
	return node[make_pair(x, y)];
}

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) {
	
	for(int i = 0; i < X.size(); i++)
		line.push_back(event(i, i, H[i]));
	
	for(int i = 0; i < L.size(); i++)
		line.push_back(event(L[i], R[i], Y[i]));
	
	sort(line.begin(), line.end());
	last = vector<int> (X.size(), 0);
	
	set<int> torres;
	for(int i = 0; i < line.size(); i++){
		int l = line[i].l, r = line[i].r, y = line[i].h;
		if(l == r) continue;
		int lV = create(l, y);
		int rV = create(r, y);
		ar[lV].push_back(rV);
		wg[lV].push_back(abs(X[r] - X[l]));
	}
	for(int i = 0; i < X.size(); i++)
		create(i, 0);
	dijkstra(create(S, 0));
	if(dist[create(G, 0)] >= INF) dist[create(G, 0)] = -1;
	return dist[create(G, 0)];
}

void dijkstra(int ini){
	dist[ini] = 0;
	set<pair<long long, int> > s;
	for(int i = 0; i <= ar.size(); i++)
		s.insert(make_pair(dist[i], i));
	while(!s.empty()){
		int cur = s.begin()->second;
		if(dist[cur] >= INF) break;
		marc[cur] = 1;
		s.erase(s.begin());
		for(int i = 0; i < ar[cur].size(); i++){
			int viz = ar[cur][i];
			if(marc[viz]) continue;
			s.erase(make_pair(dist[viz], viz));
			dist[viz] = min(dist[viz], dist[cur] + wg[cur][i]);
			s.insert(make_pair(dist[viz], viz));
		}
	}
}

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:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i = 0; i < X.size(); i++)
      |                 ~~^~~~~~~~~~
walk.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i = 0; i < L.size(); i++)
      |                 ~~^~~~~~~~~~
walk.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 0; i < line.size(); i++){
      |                 ~~^~~~~~~~~~~~~
walk.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for(int i = 0; i < X.size(); i++)
      |                 ~~^~~~~~~~~~
walk.cpp: In function 'void dijkstra(int)':
walk.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i = 0; i <= ar.size(); i++)
      |                 ~~^~~~~~~~~~~~
walk.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for(int i = 0; i < ar[cur].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 197 ms 16464 KB Output is correct
2 Incorrect 941 ms 52760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 197 ms 16464 KB Output is correct
2 Incorrect 941 ms 52760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -