Submission #726182

# Submission time Handle Problem Language Result Execution time Memory
726182 2023-04-18T16:25:16 Z GusterGoose27 Wild Boar (JOI18_wild_boar) C++17
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, bool> plb;
typedef pair<ll, int> pli;

const int MAXN = 500;
const int MAX_PATH = 1e5;
const ll inf = 1e15;
int n, m, t, l;

class path {
public:
	ll len;
	int s, e;
	path(ll l, int s, int e) : len(l), s(s), e(e) {}
	path() {}
};

int hsh(int i, int j) {
	return n*i+j; // j is prev node, i is cur node
}

vector<pii> edges[MAXN];
vector<pii> edges2[MAXN*MAXN];
ll dist[MAXN*MAXN][MAXN*MAXN];
int seq[MAX_PATH];

void dijkstra(int s) {
	priority_queue<pli, vector<pli>, greater<pli>> pq;
	fill(dist[s], dist[s]+n*n, inf);
	dist[s][s] = 0;
	pq.push(pli(0, s));
	while (!pq.empty()) {
		pii tp = pq.top();
		pq.pop();
		if (dist[s][tp.second] < tp.first) continue;
		for (pii e: edges2[tp.second]) {
			ll ndist = tp.first+e.second;
			if (ndist < dist[s][e.first]) {
				dist[s][e.first] = ndist;
				pq.push(pli(ndist, e.first));
			}
		}
	}
}

ll dp[MAX_PATH][MAXN];

ll make_dp() {
	fill(dp[l-1], dp[l-1]+n, 0);
	for (int i = l-2; i > 0; i--) {
		for (pii j: edges[seq[i]]) {
			dp[i][j.first] = inf;
			for (pii k: edges[seq[i+1]]) {
				dp[i][j.first] = min(dp[i][j.first], dp[i+1][k.first]+dist[hsh(seq[i],j.first)][hsh(seq[i+1], k.first)]);
			}
		}
	}
	ll ans = inf;
	for (pii i: edges[seq[0]]) 
		for (pii j: edges[seq[1]]) ans = min(ans, dp[1][j.first]+i.second+dist[hsh(i.first, seq[0])][hsh(seq[1], j.first)]);
	if (ans == inf) return -1;
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m >> t >> l;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c; a--; b--;
		edges[a].push_back(pii(b, c));
		edges[b].push_back(pii(a, c));
	}
	for (int i = 0; i < n; i++) {
		for (pii j: edges[i]) {
			for (pii k: edges[i]) {
				if (k.first == j.first) continue;
				edges2[hsh(i, j.first)].push_back(pii(hsh(k.first, i), k.second));
			}
		}
	}
	for (int i = 0; i < n*n; i++) {
		dijkstra(i);
	}
	for (int i = 0; i < l; i++) {
		cin >> seq[i]; seq[i]--;
	}
	for (int i = 0; i < t; i++) {
		int p, v; cin >> p >> v;
		p--; v--;
		seq[p] = v;
		cout << make_dp() << "\n";
	}
}

Compilation message

/tmp/cc4e2YFT.o: in function `__tcf_0':
wild_boar.cpp:(.text+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `edges' defined in .bss section in /tmp/cc4e2YFT.o
/tmp/cc4e2YFT.o: in function `__tcf_1':
wild_boar.cpp:(.text+0xe9): relocation truncated to fit: R_X86_64_PC32 against symbol `edges2' defined in .bss section in /tmp/cc4e2YFT.o
/tmp/cc4e2YFT.o: in function `hsh(int, int)':
wild_boar.cpp:(.text+0x137): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cc4e2YFT.o
/tmp/cc4e2YFT.o: in function `make_dp()':
wild_boar.cpp:(.text+0x15b): relocation truncated to fit: R_X86_64_PC32 against symbol `l' defined in .bss section in /tmp/cc4e2YFT.o
wild_boar.cpp:(.text+0x162): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cc4e2YFT.o
wild_boar.cpp:(.text+0x1bd): relocation truncated to fit: R_X86_64_PC32 against symbol `edges' defined in .bss section in /tmp/cc4e2YFT.o
wild_boar.cpp:(.text+0x1fb): relocation truncated to fit: R_X86_64_PC32 against symbol `edges' defined in .bss section in /tmp/cc4e2YFT.o
wild_boar.cpp:(.text+0x2c0): relocation truncated to fit: R_X86_64_PC32 against symbol `edges' defined in .bss section in /tmp/cc4e2YFT.o
wild_boar.cpp:(.text+0x2ee): relocation truncated to fit: R_X86_64_PC32 against symbol `edges' defined in .bss section in /tmp/cc4e2YFT.o
/tmp/cc4e2YFT.o: in function `dijkstra(int)':
wild_boar.cpp:(.text+0x3d8): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/cc4e2YFT.o
wild_boar.cpp:(.text+0x4e9): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status