답안 #55163 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55163	2018-07-06T07:30:40 Z	윤교준(#1528)	날다람쥐 (JOI14_ho_t4)	C++11	50 / 100	323 ms	16956 KB

2014_ho_t4

#include <bits/stdc++.h>
#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 upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
void fuk() { exit(-1); }

const int MAXN = 100005;
const int MAXM = 300005;

priority_queue<pli, vector<pli>, greater<pli>> PQ;

vector<pii> G[MAXN];

ll D[2][MAXN];

int A[MAXM], B[MAXM], C[MAXM];

int H[MAXN];

ll Ans = INFLL;
int N, M, X, MXH;

void f(int i, ll h, ll dst) {
	h = (h <= 0 ? 0 : 1);
	if(D[h][i] <= dst) return;
	D[h][i] = dst;
	PQ.push(pli(dst, i*2 + h));
}

int main() {
    //freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	cin >> N >> M >> X;
	for(int i = 1; i <= N; i++) cin >> H[i];
	for(int i = 1; i <= M; i++) cin >> A[i] >> B[i] >> C[i];

	for(int i = 1, a, b, c; i <= M; i++) {
		a = A[i]; b = B[i]; c = C[i];
		if(c <= H[a]) G[a].eb(b, c);
		if(c <= H[b]) G[b].eb(a, c);
	}

	for(int i = 0; i < 2; i++) fill(D[i], D[i]+N+1, INFLL);
	f(1, X, 0);

	for(; !PQ.empty();) {
		int idx, hi; ll dst;
		tie(dst, idx) = PQ.top(); PQ.pop();
		hi = idx&1; idx >>= 1;
		if(D[hi][idx] < dst) continue;
		if(idx == N) {
            if(!hi) {
                upmin(Ans, dst + H[N]);
            } else {
                ll h = H[N] - dst;
                upmin(Ans, dst + H[N] - h);
            }
            continue;
		}

		for(pii e : G[idx]) {
			int nidx = e.first, c = e.second;
			if(!hi) {
				ll ndst = dst + c * 2;
				f(nidx, X - ndst, ndst);
			} else {
				ll h = X - dst;
				ll ndst = INFLL;
				if(H[nidx] < h-c) {
					ndst = dst + h - H[nidx];
				} else if(c <= h) {
					ndst = dst + c;
				} else {
					ndst = dst + c * 2 - h;
				}

				f(nidx, X - ndst, ndst);
			}
		}
	}

	if(INFLL <= Ans) puts("-1");
	else cout << Ans << endl;
	return 0;
}

Subtask #1
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2808 KB	Output is correct
2	Correct	5 ms	2940 KB	Output is correct
3	Correct	6 ms	2976 KB	Output is correct
4	Correct	5 ms	2976 KB	Output is correct
5	Correct	6 ms	2976 KB	Output is correct
6	Correct	6 ms	2976 KB	Output is correct
7	Correct	6 ms	2976 KB	Output is correct
8	Correct	5 ms	3052 KB	Output is correct
9	Correct	5 ms	3052 KB	Output is correct
10	Correct	6 ms	3132 KB	Output is correct
11	Correct	5 ms	3132 KB	Output is correct
12	Correct	6 ms	3132 KB	Output is correct
13	Correct	5 ms	3132 KB	Output is correct
14	Correct	5 ms	3132 KB	Output is correct
15	Correct	7 ms	3132 KB	Output is correct
16	Correct	6 ms	3132 KB	Output is correct
17	Correct	5 ms	3132 KB	Output is correct
18	Correct	52 ms	3132 KB	Output is correct
19	Correct	5 ms	3132 KB	Output is correct
20	Correct	5 ms	3132 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	205 ms	11468 KB	Output is correct
2	Correct	201 ms	16360 KB	Output is correct
3	Correct	191 ms	16360 KB	Output is correct
4	Correct	255 ms	16956 KB	Output is correct
5	Correct	179 ms	16956 KB	Output is correct
6	Correct	11 ms	16956 KB	Output is correct
7	Correct	127 ms	16956 KB	Output is correct
8	Correct	323 ms	16956 KB	Output is correct
9	Correct	156 ms	16956 KB	Output is correct
10	Correct	94 ms	16956 KB	Output is correct
11	Correct	25 ms	16956 KB	Output is correct
12	Correct	116 ms	16956 KB	Output is correct
13	Correct	58 ms	16956 KB	Output is correct
14	Correct	154 ms	16956 KB	Output is correct
15	Correct	10 ms	16956 KB	Output is correct
16	Correct	194 ms	16956 KB	Output is correct
17	Correct	23 ms	16956 KB	Output is correct
18	Correct	23 ms	16956 KB	Output is correct
19	Correct	49 ms	16956 KB	Output is correct
20	Correct	24 ms	16956 KB	Output is correct

Subtask #3
0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	2808 KB	Output is correct
2	Correct	5 ms	2940 KB	Output is correct
3	Correct	6 ms	2976 KB	Output is correct
4	Correct	5 ms	2976 KB	Output is correct
5	Correct	6 ms	2976 KB	Output is correct
6	Correct	6 ms	2976 KB	Output is correct
7	Correct	6 ms	2976 KB	Output is correct
8	Correct	5 ms	3052 KB	Output is correct
9	Correct	5 ms	3052 KB	Output is correct
10	Correct	6 ms	3132 KB	Output is correct
11	Correct	5 ms	3132 KB	Output is correct
12	Correct	6 ms	3132 KB	Output is correct
13	Correct	5 ms	3132 KB	Output is correct
14	Correct	5 ms	3132 KB	Output is correct
15	Correct	7 ms	3132 KB	Output is correct
16	Correct	6 ms	3132 KB	Output is correct
17	Correct	5 ms	3132 KB	Output is correct
18	Correct	52 ms	3132 KB	Output is correct
19	Correct	5 ms	3132 KB	Output is correct
20	Correct	5 ms	3132 KB	Output is correct
21	Correct	205 ms	11468 KB	Output is correct
22	Correct	201 ms	16360 KB	Output is correct
23	Correct	191 ms	16360 KB	Output is correct
24	Correct	255 ms	16956 KB	Output is correct
25	Correct	179 ms	16956 KB	Output is correct
26	Correct	11 ms	16956 KB	Output is correct
27	Correct	127 ms	16956 KB	Output is correct
28	Correct	323 ms	16956 KB	Output is correct
29	Correct	156 ms	16956 KB	Output is correct
30	Correct	94 ms	16956 KB	Output is correct
31	Correct	25 ms	16956 KB	Output is correct
32	Correct	116 ms	16956 KB	Output is correct
33	Correct	58 ms	16956 KB	Output is correct
34	Correct	154 ms	16956 KB	Output is correct
35	Correct	10 ms	16956 KB	Output is correct
36	Correct	194 ms	16956 KB	Output is correct
37	Correct	23 ms	16956 KB	Output is correct
38	Correct	23 ms	16956 KB	Output is correct
39	Correct	49 ms	16956 KB	Output is correct
40	Correct	24 ms	16956 KB	Output is correct
41	Correct	147 ms	16956 KB	Output is correct
42	Correct	52 ms	16956 KB	Output is correct
43	Correct	110 ms	16956 KB	Output is correct
44	Incorrect	150 ms	16956 KB	Output isn't correct
45	Halted	0 ms	0 KB	-

답안 #55163

Compilation message

Subtask #1 25.0 / 25.0

Subtask #2 25.0 / 25.0

Subtask #3 0 / 50.0

Subtask #1
25.0 / 25.0

Subtask #2
25.0 / 25.0

Subtask #3
0 / 50.0