oj.uz

Submission #58238

# Submission time Handle Problem Language Result Execution time Memory
58238 2018-07-17T08:44:25 Z 윤교준(#1690) Wild Boar (JOI18_wild_boar) C++11
0 / 100
 4 ms 828 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

const bool debug = 0;
const int MAXN = 505;
const int MAXM = 1005;
const int MAXK = 100005;

priority_queue<pli, vector<pli>, greater<pli>> PQD;
ll Ddst[MAXN];

vector<int> G[MAXN];

ll D[MAXM][2][MAXM][2];

ll dp[MAXK][MAXM];

int A[MAXM], B[MAXM]; ll C[MAXM];
int E[MAXK];

int N, M, K, Q;

void process() {
	for(int i = 2; i <= K; i++) {
		for(int e : G[E[i]]) {
			ll &ret = dp[i][e];
			ret = INFLL;

			for(int ee : G[E[i-1]]) if(ee != e) {
				upmin(ret, min(INFLL, dp[i-1][ee] + D[ee][B[ee]==E[i-1]][e][A[e]==E[i]]) + C[e]);
			}
			if(debug) printf("%d %d %d :: %lld\n", i, E[i], e, ret);
		}
	}

	ll ret = INFLL;
	for(int e : G[E[K]]) upmin(ret, dp[K][e]);

	printf("%lld\n", INFLL <= ret ? -1 : ret);
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M >> Q >> K;
	for(int i = 1; i <= M; i++) cin >> A[i] >> B[i] >> C[i];
	for(int i = 1; i <= K; i++) cin >> E[i];

	for(int i = 1; i <= M; i++) {
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}
	for(int i = 1; i <= N; i++) {
		A[M+i] = i; B[M+i] = N+1;
		C[M+i] = INFLL;
		G[i].eb(M+i);
		G[N+1].eb(M+i);
	}
	N++;

	for(int i = 1; i <= N; i++) {
		for(int e : G[i]) {
			for(int j = i+1; j <= N; j++) {
				for(int ee : G[j]) {
					for(; !PQD.empty(); PQD.pop());
					fill(Ddst, Ddst+N+1, INFLL);
					Ddst[i] = 0;
					PQD.push(pli(0, i));
					bool flag = false;

					for(; !PQD.empty();) {
						int idx; ll dst;
						tie(dst, idx) = PQD.top(); PQD.pop();
						if(Ddst[idx] < dst) continue;

						for(int ne : G[idx]) {
							if(ne == e || ne == ee) continue;
							ll ndst = dst + C[ne];
							int nidx = A[ne] + B[ne] - idx;
							if(Ddst[nidx] <= ndst) continue;

							Ddst[nidx] = ndst;
							PQD.push(pli(ndst, nidx));

							if(nidx == j) {
								flag = true;
								break;
							}
						}
						if(flag) break;
					}

					ll ret = flag ? Ddst[j] : INFLL;
					D[e][B[e]==i][ee][B[ee]==j] = ret;
					D[ee][B[ee]==j][e][B[e]==i] = ret;
				}
			}
		}
	}

	if(debug) {
		for(int i = 1; i <= M; i++) for(int j = 1; j <= M; j++)
			printf("%d %d : %lld %lld %lld %lld\n", i, j, D[i][0][j][0], D[i][0][j][1], D[i][1][j][0], D[i][1][j][1]);
	}

	for(int qi = 0, a, b; qi < Q; qi++) {
		cin >> a >> b;
		E[a] = b;
		process();
	}

	return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 508 KB Output is correct
2 Correct 4 ms 616 KB Output is correct
3 Correct 3 ms 684 KB Output is correct
4 Correct 2 ms 720 KB Output is correct
5 Correct 3 ms 720 KB Output is correct
6 Correct 3 ms 816 KB Output is correct
7 Correct 3 ms 816 KB Output is correct
8 Correct 2 ms 828 KB Output is correct
9 Incorrect 2 ms 828 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 508 KB Output is correct
2 Correct 4 ms 616 KB Output is correct
3 Correct 3 ms 684 KB Output is correct
4 Correct 2 ms 720 KB Output is correct
5 Correct 3 ms 720 KB Output is correct
6 Correct 3 ms 816 KB Output is correct
7 Correct 3 ms 816 KB Output is correct
8 Correct 2 ms 828 KB Output is correct
9 Incorrect 2 ms 828 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 508 KB Output is correct
2 Correct 4 ms 616 KB Output is correct
3 Correct 3 ms 684 KB Output is correct
4 Correct 2 ms 720 KB Output is correct
5 Correct 3 ms 720 KB Output is correct
6 Correct 3 ms 816 KB Output is correct
7 Correct 3 ms 816 KB Output is correct
8 Correct 2 ms 828 KB Output is correct
9 Incorrect 2 ms 828 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 508 KB Output is correct
2 Correct 4 ms 616 KB Output is correct
3 Correct 3 ms 684 KB Output is correct
4 Correct 2 ms 720 KB Output is correct
5 Correct 3 ms 720 KB Output is correct
6 Correct 3 ms 816 KB Output is correct
7 Correct 3 ms 816 KB Output is correct
8 Correct 2 ms 828 KB Output is correct
9 Incorrect 2 ms 828 KB Output isn't correct
10 Halted 0 ms 0 KB -