Submission #938127

#	Time	Username	Problem	Language	Result	Execution time	Memory
938127		CpDark	OBELISK (NOI14_obelisk)	C++17	25 / 25	85 ms	33524 KiB

obelisk

#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18 + 9;

long long dist1D(long long x, bool useHor, bool useVert, int m) {
    if (m == 1) return x;
    if (!x) return 0;
    if (!useHor && !useVert) return inf;
    if (!useHor) return x;
    long long v = x / (m + 1);
    long long sx = v * (m + 1);
    if (sx == x) return 2 * v - 2;
    if (!useVert) return inf;
    long long fromFront = max(0LL, 2 * v - 2) + x - sx;
    long long fromBack = 2 * v + (sx + m + 1) - x;
    return min(fromFront, fromBack);
}

long long getDist(pair<int, int> a, pair<int, int> b, int m) {
    int x = abs(a.first - b.first), y = abs(a.second - b.second);
    long long ans = inf;
    for (int useVert = 0; useVert < 2; ++useVert) {
        for (int useHor = 0; useHor < 2; ++useHor) {
            ans = min(ans, 2 * (useHor + useVert) + dist1D(x, useHor, useVert, m) + dist1D(y, useVert, useHor, m));
        }
    }
    return ans;
}

vector<vector<pair<int, long long>>> graph;
vector<long long> dist;

void dijkstra(int root, int n) {
    dist.resize(n, inf);
    vector<bool> done(n, false);
	priority_queue<pair<int, long long>, vector<pair<int, long long>>, greater<pair<int, long long>>> pq;

	dist[root] = 0;
	pq.push({ 0,root });

	while (!pq.empty()) {
		int v = pq.top().second;
		pq.pop();

		if (done[v]) continue;
		done[v] = true;

		for (int i = 0; i < graph[v].size(); i++) {
			int u = graph[v][i].first;
			long long w = graph[v][i].second;
			if (dist[u] > dist[v] + w) {
				dist[u] = dist[v] + w;
				pq.push({ dist[u],u });
			}
		}	
	}
}



long long solve(int n, int m, pair<int, int> s, pair<int, int>e, vector<vector<pair<int, int>>> holes) {    
    int counter = 0;
    for (int i = 0;i < holes.size();i++) counter += holes[i].size();
    vector<vector<int>> id(holes.size());
    graph.resize(counter + 2);

    // build graph
    int index = 1;
    for (int i = 0;i < holes.size();i++) {
        id[i].resize(holes[i].size());
        for (int j = 0;j < holes[i].size();j++) {
            id[i][j] = index++;
            // if last level connect to end point
            if (i == holes.size() - 1) graph[id[i][j]].push_back({ counter + 1,getDist(holes[i][j],e, m) });
            // if first level connect start point
            if (i == 0) {
                graph[0].push_back({ id[i][j], getDist(s,holes[i][j], m) });
                continue;
            }
            // connect this level to previous level
            for (int k = 0;k < holes[i - 1].size();k++) {
                graph[id[i - 1][k]].push_back({ id[i][j], getDist(holes[i - 1][k], holes[i][j], m) });
            }
        }
    }

    dijkstra(0, index + 1);
    return dist[index];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    pair<int, int> S, E;
    cin >> N >> M >> S.first >> S.second >> E.first >> E.second;

    vector<vector<pair<int, int>>> H(N - 1);
    for (int i = 0;i < N - 1;i++) {
        cin >> K;
        H[i].resize(K);
        for (int j = 0;j < K;j++) cin >> H[i][j].first >> H[i][j].second;
    }

    cout << solve(N, M, S, E, H);
    return 0;
}

Compilation message (stderr)

obelisk.cpp: In function 'void dijkstra(int, int)':
obelisk.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int i = 0; i < graph[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
obelisk.cpp: In function 'long long int solve(int, int, std::pair<int, int>, std::pair<int, int>, std::vector<std::vector<std::pair<int, int> > >)':
obelisk.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0;i < holes.size();i++) counter += holes[i].size();
      |                    ~~^~~~~~~~~~~~~~
obelisk.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int i = 0;i < holes.size();i++) {
      |                    ~~^~~~~~~~~~~~~~
obelisk.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int j = 0;j < holes[i].size();j++) {
      |                        ~~^~~~~~~~~~~~~~~~~
obelisk.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             if (i == holes.size() - 1) graph[id[i][j]].push_back({ counter + 1,getDist(holes[i][j],e, m) });
      |                 ~~^~~~~~~~~~~~~~~~~~~
obelisk.cpp:81:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for (int k = 0;k < holes[i - 1].size();k++) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 7 / 7