Submission #136737

#	Time	Username	Problem	Language	Result	Execution time	Memory
136737		E869120	Wild Boar (JOI18_wild_boar)	C++14	47 / 100	18071 ms	63140 KiB

wild_boar

#include <iostream>
#include <tuple>
#include <queue>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

const int MAX_N = 2009;
const int MAX_CANDIDATE = 2;
const int MAX_PREV = 3;
const int MAX_V = 6;
const long long INF = (((1LL << 41) - 1LL) << 22LL);

int N, M, L, T, A[MAX_N], B[MAX_N], C[MAX_N], P[100009], cntv[MAX_N], forced[MAX_N];
vector<pair<int, long long>> G[MAX_N];
long long dist[MAX_N][MAX_N][MAX_V];
pair<long long, int> dp[100009][2];

int cnt1[MAX_N][MAX_N], cnt2[MAX_N], cnt3[MAX_N];
long long R[19]; int sz;

void hosei() {
	int dt = 0, kinds = 0;
	for (int i = 0; i < sz; i++) {
		int v1 = ((R[i] >> 11) & 2047LL), v2 = (R[i] & 2047LL);
		if (cnt1[v1][v2] >= 1) continue;
		if (cnt2[v1] >= MAX_PREV) continue;
		if (cnt3[v2] >= MAX_CANDIDATE) continue;
		R[dt] = R[i]; dt++;
		cnt1[v1][v2]++; cnt2[v1]++; cnt3[v2]++;
	}
	for (int i = 0; i < dt; i++) {
		int v1 = ((R[i] >> 11) & 2047LL), v2 = (R[i] & 2047LL);
		cnt1[v1][v2] = 0; cnt2[v1] = 0; cnt3[v2] = 0;
	}
	sz = dt;
}

void init(int pos) {
	for (int i = 1; i <= N; i++) {
		cntv[i] = -1; forced[i] = -(1 << 30);
		for (int j = 0; j < MAX_V; j++) { dist[pos][i][j] = INF; }
	}

	priority_queue<long long, vector<long long>, greater<long long>>Q;
	dist[pos][pos][0] = 0LL;

	for (int i = 0; i < G[pos].size(); i++) {
		int to = G[pos][i].first; long long cost = G[pos][i].second;
		dist[pos][to][0] = (cost << 22) + 1LL * (to << 11) + 1LL * pos;
		Q.push(1LL * (cost << 11) + 1LL * to);
	}

	// 各 dist に対する上位 6 点を記録する

	while (!Q.empty()) {
		int cur = (Q.top() & 2047); Q.pop();
		if (forced[cur] == cntv[cur]) continue;
		cntv[cur] = forced[cur];

		for (int i = 0; i < G[cur].size(); i++) {
			int to = G[cur][i].first; long long cost = G[cur][i].second;

			sz = 0;
			for (int j = 0; j < MAX_V; j++) {
				if (dist[pos][to][j] != INF) { R[sz] = dist[pos][to][j]; sz++; }
			}

			for (int j = 0; j < MAX_V; j++) {
				if ((dist[pos][cur][j] & 2047LL) == to) continue;
				if (dist[pos][cur][j] == INF) break;
				long long val = (dist[pos][cur][j] >> 22) + cost;
				long long v1 = ((dist[pos][cur][j] >> 11) & 2047LL);
				long long v2 = cur; if (v1 == 0) v1 = to;
				R[sz] = (val << 22) + (v1 << 11) + v2; sz++;
			}
			sort(R, R + sz); hosei();

			long long flag = (1LL << 60);
			for (int j = 0; j < min(sz, MAX_V); j++) {
				if (dist[pos][to][j] > R[j]) {
					flag = min(flag, (R[j] >> 22));
					flag = true;
					dist[pos][to][j] = R[j];
				}
			}
			if (flag < (1LL << 41)) {
				Q.push(1LL * (flag << 11) + 1LL * to);
				cntv[to] = flag;
			}
		}
	}
}

long long solve() {
	for (int i = 1; i <= L; i++) {
		dp[i][0] = make_pair(1LL << 60, -1);
		dp[i][1] = make_pair(1LL << 60, -1);
	}
	for (int i = 0; i < min(2, (int)G[P[1]].size()); i++) {
		dp[1][i] = make_pair(0LL, G[P[1]][i].first);
	}

	for (int t = 2; t <= L; t++) {
		vector<pair<long long, int>> vec;
		int from = P[t - 1], to = P[t];

		for (int j = 0; j < 2; j++) {
			if (dp[t - 1][j].first == (1LL << 60)) continue;
			for (int k = 0; k < MAX_V; k++) {
				if (dist[from][to][k] == INF) continue;
				long long v0 = ((dist[from][to][k] >> 22));
				long long v1 = ((dist[from][to][k] >> 11) & 2047LL);
				long long v2 = ((dist[from][to][k]) & 2047LL);
				if (t >= 3 && dp[t - 1][j].second == v1) continue;
				vec.push_back(make_pair(dp[t - 1][j].first + v0, v2));
			}
		}
		sort(vec.begin(), vec.end());
		for (int j = 0; j < vec.size(); j++) {
			if (j == 0) dp[t][0] = vec[j];
			else if (vec[j].second != vec[j - 1].second) {
				dp[t][1] = vec[j]; break;
			}
		}
	}

	if (dp[L][0].first == (1LL << 60)) return -1LL;
	return dp[L][0].first;
}

int main() {
	scanf("%d%d%d%d", &N, &M, &T, &L);
	for (int i = 1; i <= M; i++) {
		scanf("%d%d%d", &A[i], &B[i], &C[i]);
		G[A[i]].push_back(make_pair(B[i], C[i]));
		G[B[i]].push_back(make_pair(A[i], C[i]));
	}
	for (int i = 1; i <= L; i++) scanf("%d", &P[i]);

	for (int i = 1; i <= N; i++) init(i);

	for (int i = 1; i <= T; i++) {
		int v1, v2; scanf("%d%d", &v1, &v2);
		P[v1] = v2;
		printf("%lld\n", solve());
	}
	return 0;
}

Compilation message (stderr)

wild_boar.cpp:9:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
wild_boar.cpp: In function 'void hosei()':
wild_boar.cpp:26:14: warning: unused variable 'kinds' [-Wunused-variable]
  int dt = 0, kinds = 0;
              ^~~~~
wild_boar.cpp: In function 'void init(int)':
wild_boar.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
wild_boar.cpp:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < G[cur].size(); i++) {
                   ~~^~~~~~~~~~~~~~~
wild_boar.cpp: In function 'long long int solve()':
wild_boar.cpp:123:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < vec.size(); j++) {
                   ~~^~~~~~~~~~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &N, &M, &T, &L);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &A[i], &B[i], &C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:142:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= L; i++) scanf("%d", &P[i]);
                               ~~~~~^~~~~~~~~~~~~
wild_boar.cpp:147:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int v1, v2; scanf("%d%d", &v1, &v2);
               ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38