| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 136735 | 2019-07-26T07:55:22 Z | E869120 | Wild Boar (JOI18_wild_boar) | C++14 | 2 ms | 504 KB |
#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++) {
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) || v0 == (1LL << 60)) 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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 504 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 504 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 504 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 504 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |