| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58249 |
2018-07-17T08:59:00 Z |
윤교준(#1690) |
Wild Boar (JOI18_wild_boar) |
C++11 |
|
3 ms |
504 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 = 505;
const int MAXK = 55;
priority_queue<pair<ll, pair<int, pii>>, vector<pair<ll, pair<int, pii>>>, greater<pair<ll, pair<int, pii>>>> PQ;
ll DP[MAXK][MAXN][MAXM];
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() {
PQ.push(pair<ll, pair<int, pii>>(0, pair<int, pii>(1, pii(E[1], -1))));
int cnt = 0;
for(; !PQ.empty();) {
cnt++;
ll dst;
int idx, eidx, pve;
dst = PQ.top().first;
eidx = PQ.top().second.first;
tie(idx, pve) = PQ.top().second.second;
PQ.pop();
if(eidx == K) {
printf("%lld\n", dst);
return;
}
if(100000 < cnt) break;
for(int e : G[idx]) if(e != pve) {
ll ndst = dst + C[e];
int nidx = A[e] + B[e] - idx;
int neidx = eidx;
if(E[eidx+1] == nidx) neidx++;
PQ.push(pair<ll, pair<int, pii>>(ndst, pair<int, pii>(neidx, pii(nidx, e))));
}
}
puts("-1");
}
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; 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
