oj.uz

답안 #393630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
393630 2021-04-24T07:07:30 Z JimmyZJX 고대 책들 (IOI17_books) C++14
0 / 100
 1 ms 332 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <numeric>

using namespace std;

typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
typedef vector<vector<vector<int>>> Viii;
typedef vector<vector<pair<int, int>>> Vip;

#define forR(i, n) for (int i = 0; i < (n); i++)

const int INF = 1 << 25;

LL minimum_walk(Vi p, int s) {

	int n = p.size();

	LL ans = 0;
	Vi g(n);
	Vii gps(1); // dummy
	int gn = 0; // [1, gn]

	forR(i, n) {
		if (p[i] == i) continue;

		gn++;
		Vi gp;

		int h = p[i];
		int pos = i;
		g[i] = gn; gp.push_back(i);
		while (h != i) {
			ans += abs(h - pos);
			pos = h;
			g[h] = gn; gp.push_back(h);
			swap(h, p[h]);
		}
		ans += abs(pos - i);
		p[i] = i;
		gps.push_back(gp);
	}


	Vii nbs(n);
	Vii nbDs(n);

	for (int i = 1; i <= gn; i++) {
		auto& gp = gps[i];
		map<int, int> distToGp;
		distToGp[0] = INF;
		for (int j : gp) {
			distToGp[0] = min(distToGp[0], abs(j - s));
			// left
			for (int k = j - 1; k >= 0; k--) {
				if (g[k] > 0) {
					if (g[k] != g[i]) {
						// other group
						int d = abs(j - k);
						if (distToGp.count(g[k]) > 0) {
							distToGp[g[k]] = min(distToGp[g[k]], d);
						} else {
							distToGp[g[k]] = d;
						}
					}
					break;
				}
			}
			// right
			for (int k = j + 1; k < n; k++) {
				if (g[k] > 0) {
					if (g[k] != g[i]) {
						// other group
						int d = abs(j - k);
						if (distToGp.count(g[k]) > 0) {
							distToGp[g[k]] = min(distToGp[g[k]], d);
						} else {
							distToGp[g[k]] = d;
						}
					}
					break;
				}
			}
		}

		for (auto p : distToGp) {
			nbs[i].push_back(p.first);
			nbDs[i].push_back(p.second);
		}
		nbs[0].push_back(i);
		nbDs[0].push_back(distToGp[0]);
	}

	// MST
	LL mst = 0;
	Vb vis(gn + 1);
	set<pair<int, int>> minQ; // {dist, gp}
	minQ.insert({ 0, 0 });
	while (!minQ.empty()) {
		auto t = *minQ.begin(); minQ.erase(t);
		int gp = t.second;
		if (vis[gp]) continue;
		mst += t.first;
		vis[gp] = true;
		forR(i, nbs[gp].size()) {
			minQ.insert({ nbDs[gp][i], nbs[gp][i] });
		}
	}

	return ans + mst * 2;

}

#ifdef TEST_LOCAL

int main() {
	auto r = minimum_walk(Vi{ 0, 2, 3, 1 }, 0);

	return 0;
}
#endif

Compilation message

books.cpp: In function 'LL minimum_walk(Vi, int)':
books.cpp:28:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 | #define forR(i, n) for (int i = 0; i < (n); i++)
      |                                      ^
books.cpp:122:3: note: in expansion of macro 'forR'
  122 |   forR(i, nbs[gp].size()) {
      |   ^~~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Incorrect 1 ms 204 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Incorrect 1 ms 204 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Incorrect 1 ms 204 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB 3rd lines differ - on the 1st token, expected: '3304', found: '4106'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Incorrect 1 ms 204 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
7 Halted 0 ms 0 KB -