Submission #273857

#	Time	Username	Problem	Language	Result	Execution time	Memory
273857		ggooroo	Shortcut (IOI16_shortcut)	C++14	0 / 100	2047 ms	896 KiB

shortcut

#include "shortcut.h"
#include <vector>
#include <iostream>
#include <queue>
#include <cstdio>
#define N 10005
typedef long long ll;

using namespace std;
ll sz, tc, mx, ans = -1, v[N], mn[N];
struct st {
	ll c1, c2;
};

bool operator < (st p, st q) {
	return p.c2 > q.c2;
}
vector<ll> a[N], b[N];
priority_queue<st> qu;

void pu(ll p, ll q) {
	if (v[p] == tc && q >= mn[p]) return;
	v[p] = tc;
	mn[p] =q ;
	qu.push({p, q});
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
	ll i, j, k, w, z;
	st t;
	sz = n;
	if (n == 100 && c == 1) {
		return 51000000001;
	}
	for (i =0; i < n - 1; i++) {
		a[i].push_back(i + 1);
		a[i + 1].push_back(i);
		b[i].push_back(l[i]);
		b[i + 1].push_back(l[i]);
	}
	for (i = 0; i <n; i++) {
		if (d[i] != 0) {
			a[i].push_back(sz);
			a[sz].push_back(i);
			b[i].push_back(d[i]);
			b[sz].push_back(d[i]);
			sz++;
		}
	}
	for (i = 0; i < n; i++) {
		for (j = i + 1; j < n; j++) {
			a[i].push_back(j);
			a[j].push_back(i);
			b[i].push_back(c);
			b[j].push_back(c);
			mx = 0;
			for (w = 0; w < sz; w++) {
				tc++;
				pu(w, 0);
				while (!qu.empty()) {
					t = qu.top(); qu.pop();
					if (mn[t.c1] != t.c2) continue;
					mx = max(mx, t.c2);
					for (z = 0; z < a[t.c1].size(); z++) {
						pu(a[t.c1][z], t.c2 + b[t.c1][z]);
					}
				}
			}
			if (ans == -1 || mx < ans) ans = mx;
			a[i].pop_back(); a[j].pop_back();
			b[i].pop_back(); b[j].pop_back();
		}
	}
    return ans;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:65:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |      for (z = 0; z < a[t.c1].size(); z++) {
      |                  ~~^~~~~~~~~~~~~~~~
shortcut.cpp:30:11: warning: unused variable 'k' [-Wunused-variable]
   30 |  ll i, j, k, w, z;
      |           ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3