답안 #61745 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61745	2018-07-26T13:56:34 Z	cki86201	Wild Boar (JOI18_wild_boar)	C++11	62 / 100	12932 ms	413220 KB

wild_boar

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;

typedef pair<ll, int> pli;

int N, M, T, L;
t3 edgen[4040];
int edgec[2020][2020];
vector <pii> IE[2020];
vector <int> nume[2020];
vector <int> numl[2020], numr[2020];
vector <pii> E[20020];
int cs;
void addedge(int x, int y, int c) {
	E[x].pb(pii(c, y));
}

ll dis[4040][4040], dtemp[12020];
int X[100010];
pii query[100010];

pll tmn[4040][2020][2];

int main() {
	memset(edgec, -1, sizeof edgec);
	scanf("%d%d%d%d", &N, &M, &T, &L);
	rep(i, M) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		edgen[i<<1] = t3(x, y, z);
		edgec[x][y] = i<<1;
		edgen[i<<1|1] = t3(y, x, z);
		edgec[y][x] = i<<1|1;
		nume[x].pb(cs++);
		nume[y].pb(cs++);
		IE[x].pb(pii(z, y));
		IE[y].pb(pii(z, x));
	}
	for(int i=1;i<=N;i++) {
		int l = szz(IE[i]);
		numl[i].resize(l);
		numr[i].resize(l);
		rep(j, l) numl[i][j] = cs++;
		rep(j, l) numr[i][j] = cs++;
		for(int j=1;j<l;j++) {
			int x = numl[i][j-1], y = numl[i][j];
			addedge(y, x, 0);
			x = numr[i][j-1], y = numr[i][j];
			addedge(x, y, 0);
		}
		rep(j, l) {
			addedge(numl[i][j], nume[i][j], 0);
			addedge(numr[i][j], nume[i][j], 0);
		}
		rep(j, l) {
			int x = nume[i][j] ^ 1, len = get<2>(edgen[x]);
			if(j) addedge(x, numl[i][j-1], len);
			if(j < l-1) addedge(x, numr[i][j+1], len);
		}
	}
	rep(st, 2*M) {
		rep(i, cs) dtemp[i] = 1e18;
		dtemp[st] = 0;
		priority_queue <pli, vector<pli>, greater<pli> > pq;
		pq.push(pli(0, st));
		while(!pq.empty()) {
			pli t = pq.top(); pq.pop();
			if(dtemp[t.Se] != t.Fi) continue;
			for(pii e : E[t.Se]) {
				if(t.Fi + e.Fi < dtemp[e.Se]) {
					dtemp[e.Se] = t.Fi + e.Fi;
					pq.push(pli(dtemp[e.Se], e.Se));
				}
			}
		}
		rep(i, 2*M) dis[st][i] = dtemp[i];
	}
	
	rep(i, 4040) rep(j, 2020) rep(k, 2) tmn[i][j][k] = pll(1e18, -1);
	
	for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) {
		int si = szz(IE[i]);
		int sj = szz(IE[j]);
		
		rep(k, si) {
			int eidx = nume[i][k];
			rep(l, sj) {
				int fidx = nume[j][l] ^ 1;
				pll p = pll(dis[eidx][fidx] + get<2>(edgen[fidx]), get<0>(edgen[fidx]));
				if(tmn[eidx][j][0] > p) tmn[eidx][j][1] = tmn[eidx][j][0], tmn[eidx][j][0] = p;
				else if(tmn[eidx][j][1] > p) tmn[eidx][j][1] = p;
			}
		}
	}
	
	for(int i=1;i<=L;i++) scanf("%d", X+i);
	for(int i=1;i<=T;i++) {
		int x, y; scanf("%d%d", &x, &y);
		query[i] = pii(x, y);
	}
	if(T > 1) return 0;
	X[query[1].Fi] = query[1].Se;
	int ST = X[1];
	ll dp[2020] = {}, tdp[2020];
	for(int i=1;i<=N;i++) dp[i] = 1e18;
	for(int i=1;i<=N;i++) {
		if(edgec[ST][i] != -1) dp[i] = 0;
	}
	for(int i=2;i<=L;i++) {
		int pre = X[i-1], nxt = X[i];
		for(int j=1;j<=N;j++) tdp[j] = 1e18;
		for(int j=1;j<=N;j++) if(dp[j] < 1e18) {
			int eidx = edgec[pre][j];
			rep(u, 2) if(tmn[eidx][nxt][u].Fi < 1e18) {
				int fj = (int)tmn[eidx][nxt][u].Se;
				tdp[fj] = min(tdp[fj], dp[j] + tmn[eidx][nxt][u].Fi);
			}
		}
		if(i == L) break;
		pll wp[2]; rep(u, 2) wp[u] = pll(1e18, -1);
		for(int j=1;j<=N;j++) {
			pll p = pll(tdp[j], j);
			if(wp[0] > p) wp[1] = wp[0], wp[0] = p;
			else if(wp[1] > p) wp[1] = p;
		}
		for(int j=1;j<=N;j++) {
			if(edgec[nxt][j] != -1) {
				if(wp[0].Se != j) dp[j] = wp[0].Fi;
				else dp[j] = wp[1].Fi;
			}
			else dp[j] = 1e18;
		}
	}
	ll ans = 1e18;
	for(int i=1;i<=N;i++) ans = min(ans, tdp[i]);
	if(ans == 1e18) puts("-1");
	else printf("%lld\n", ans);
	
	return 0;
}

Compilation message

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:54: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:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:124:29: 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", X+i);
                        ~~~~~^~~~~~~~~~~
wild_boar.cpp:126:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	209 ms	272544 KB	Output is correct
2	Correct	267 ms	272612 KB	Output is correct
3	Correct	245 ms	272776 KB	Output is correct
4	Correct	251 ms	272804 KB	Output is correct
5	Correct	266 ms	272804 KB	Output is correct
6	Correct	199 ms	272832 KB	Output is correct
7	Correct	254 ms	272852 KB	Output is correct
8	Correct	293 ms	272852 KB	Output is correct
9	Correct	249 ms	272852 KB	Output is correct
10	Correct	207 ms	272852 KB	Output is correct
11	Correct	226 ms	272852 KB	Output is correct
12	Correct	251 ms	272996 KB	Output is correct
13	Correct	253 ms	272996 KB	Output is correct
14	Correct	272 ms	272996 KB	Output is correct
15	Correct	239 ms	272996 KB	Output is correct
16	Correct	289 ms	272996 KB	Output is correct
17	Correct	205 ms	272996 KB	Output is correct
18	Correct	206 ms	272996 KB	Output is correct
19	Correct	231 ms	272996 KB	Output is correct
20	Correct	242 ms	272996 KB	Output is correct
21	Correct	218 ms	272996 KB	Output is correct
22	Correct	212 ms	272996 KB	Output is correct
23	Correct	276 ms	272996 KB	Output is correct
24	Correct	274 ms	272996 KB	Output is correct
25	Correct	219 ms	272996 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	209 ms	272544 KB	Output is correct
2	Correct	267 ms	272612 KB	Output is correct
3	Correct	245 ms	272776 KB	Output is correct
4	Correct	251 ms	272804 KB	Output is correct
5	Correct	266 ms	272804 KB	Output is correct
6	Correct	199 ms	272832 KB	Output is correct
7	Correct	254 ms	272852 KB	Output is correct
8	Correct	293 ms	272852 KB	Output is correct
9	Correct	249 ms	272852 KB	Output is correct
10	Correct	207 ms	272852 KB	Output is correct
11	Correct	226 ms	272852 KB	Output is correct
12	Correct	251 ms	272996 KB	Output is correct
13	Correct	253 ms	272996 KB	Output is correct
14	Correct	272 ms	272996 KB	Output is correct
15	Correct	239 ms	272996 KB	Output is correct
16	Correct	289 ms	272996 KB	Output is correct
17	Correct	205 ms	272996 KB	Output is correct
18	Correct	206 ms	272996 KB	Output is correct
19	Correct	231 ms	272996 KB	Output is correct
20	Correct	242 ms	272996 KB	Output is correct
21	Correct	218 ms	272996 KB	Output is correct
22	Correct	212 ms	272996 KB	Output is correct
23	Correct	276 ms	272996 KB	Output is correct
24	Correct	274 ms	272996 KB	Output is correct
25	Correct	219 ms	272996 KB	Output is correct
26	Correct	249 ms	273132 KB	Output is correct
27	Correct	310 ms	274552 KB	Output is correct
28	Correct	283 ms	274848 KB	Output is correct
29	Correct	573 ms	279504 KB	Output is correct
30	Correct	484 ms	279648 KB	Output is correct
31	Correct	475 ms	279732 KB	Output is correct
32	Correct	626 ms	280060 KB	Output is correct
33	Correct	615 ms	280516 KB	Output is correct
34	Correct	640 ms	280828 KB	Output is correct
35	Correct	595 ms	280848 KB	Output is correct
36	Correct	550 ms	281116 KB	Output is correct
37	Correct	554 ms	281380 KB	Output is correct
38	Correct	628 ms	281900 KB	Output is correct
39	Correct	640 ms	282052 KB	Output is correct
40	Correct	484 ms	282320 KB	Output is correct
41	Correct	617 ms	282728 KB	Output is correct
42	Correct	501 ms	282956 KB	Output is correct
43	Correct	540 ms	283280 KB	Output is correct
44	Correct	582 ms	283556 KB	Output is correct
45	Correct	619 ms	284004 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	209 ms	272544 KB	Output is correct
2	Correct	267 ms	272612 KB	Output is correct
3	Correct	245 ms	272776 KB	Output is correct
4	Correct	251 ms	272804 KB	Output is correct
5	Correct	266 ms	272804 KB	Output is correct
6	Correct	199 ms	272832 KB	Output is correct
7	Correct	254 ms	272852 KB	Output is correct
8	Correct	293 ms	272852 KB	Output is correct
9	Correct	249 ms	272852 KB	Output is correct
10	Correct	207 ms	272852 KB	Output is correct
11	Correct	226 ms	272852 KB	Output is correct
12	Correct	251 ms	272996 KB	Output is correct
13	Correct	253 ms	272996 KB	Output is correct
14	Correct	272 ms	272996 KB	Output is correct
15	Correct	239 ms	272996 KB	Output is correct
16	Correct	289 ms	272996 KB	Output is correct
17	Correct	205 ms	272996 KB	Output is correct
18	Correct	206 ms	272996 KB	Output is correct
19	Correct	231 ms	272996 KB	Output is correct
20	Correct	242 ms	272996 KB	Output is correct
21	Correct	218 ms	272996 KB	Output is correct
22	Correct	212 ms	272996 KB	Output is correct
23	Correct	276 ms	272996 KB	Output is correct
24	Correct	274 ms	272996 KB	Output is correct
25	Correct	219 ms	272996 KB	Output is correct
26	Correct	249 ms	273132 KB	Output is correct
27	Correct	310 ms	274552 KB	Output is correct
28	Correct	283 ms	274848 KB	Output is correct
29	Correct	573 ms	279504 KB	Output is correct
30	Correct	484 ms	279648 KB	Output is correct
31	Correct	475 ms	279732 KB	Output is correct
32	Correct	626 ms	280060 KB	Output is correct
33	Correct	615 ms	280516 KB	Output is correct
34	Correct	640 ms	280828 KB	Output is correct
35	Correct	595 ms	280848 KB	Output is correct
36	Correct	550 ms	281116 KB	Output is correct
37	Correct	554 ms	281380 KB	Output is correct
38	Correct	628 ms	281900 KB	Output is correct
39	Correct	640 ms	282052 KB	Output is correct
40	Correct	484 ms	282320 KB	Output is correct
41	Correct	617 ms	282728 KB	Output is correct
42	Correct	501 ms	282956 KB	Output is correct
43	Correct	540 ms	283280 KB	Output is correct
44	Correct	582 ms	283556 KB	Output is correct
45	Correct	619 ms	284004 KB	Output is correct
46	Correct	853 ms	290320 KB	Output is correct
47	Correct	12932 ms	406152 KB	Output is correct
48	Correct	10658 ms	406400 KB	Output is correct
49	Correct	9624 ms	406552 KB	Output is correct
50	Correct	11200 ms	406676 KB	Output is correct
51	Correct	10596 ms	407016 KB	Output is correct
52	Correct	11576 ms	407420 KB	Output is correct
53	Correct	11208 ms	407904 KB	Output is correct
54	Correct	10193 ms	408320 KB	Output is correct
55	Correct	10531 ms	408764 KB	Output is correct
56	Correct	11110 ms	409336 KB	Output is correct
57	Correct	10822 ms	409740 KB	Output is correct
58	Correct	9086 ms	410316 KB	Output is correct
59	Correct	9032 ms	410620 KB	Output is correct
60	Correct	8113 ms	410860 KB	Output is correct
61	Correct	8811 ms	411536 KB	Output is correct
62	Correct	7647 ms	411952 KB	Output is correct
63	Correct	7164 ms	412348 KB	Output is correct
64	Correct	2902 ms	412944 KB	Output is correct
65	Correct	2821 ms	413220 KB	Output is correct

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	209 ms	272544 KB	Output is correct
2	Correct	267 ms	272612 KB	Output is correct
3	Correct	245 ms	272776 KB	Output is correct
4	Correct	251 ms	272804 KB	Output is correct
5	Correct	266 ms	272804 KB	Output is correct
6	Correct	199 ms	272832 KB	Output is correct
7	Correct	254 ms	272852 KB	Output is correct
8	Correct	293 ms	272852 KB	Output is correct
9	Correct	249 ms	272852 KB	Output is correct
10	Correct	207 ms	272852 KB	Output is correct
11	Correct	226 ms	272852 KB	Output is correct
12	Correct	251 ms	272996 KB	Output is correct
13	Correct	253 ms	272996 KB	Output is correct
14	Correct	272 ms	272996 KB	Output is correct
15	Correct	239 ms	272996 KB	Output is correct
16	Correct	289 ms	272996 KB	Output is correct
17	Correct	205 ms	272996 KB	Output is correct
18	Correct	206 ms	272996 KB	Output is correct
19	Correct	231 ms	272996 KB	Output is correct
20	Correct	242 ms	272996 KB	Output is correct
21	Correct	218 ms	272996 KB	Output is correct
22	Correct	212 ms	272996 KB	Output is correct
23	Correct	276 ms	272996 KB	Output is correct
24	Correct	274 ms	272996 KB	Output is correct
25	Correct	219 ms	272996 KB	Output is correct
26	Correct	249 ms	273132 KB	Output is correct
27	Correct	310 ms	274552 KB	Output is correct
28	Correct	283 ms	274848 KB	Output is correct
29	Correct	573 ms	279504 KB	Output is correct
30	Correct	484 ms	279648 KB	Output is correct
31	Correct	475 ms	279732 KB	Output is correct
32	Correct	626 ms	280060 KB	Output is correct
33	Correct	615 ms	280516 KB	Output is correct
34	Correct	640 ms	280828 KB	Output is correct
35	Correct	595 ms	280848 KB	Output is correct
36	Correct	550 ms	281116 KB	Output is correct
37	Correct	554 ms	281380 KB	Output is correct
38	Correct	628 ms	281900 KB	Output is correct
39	Correct	640 ms	282052 KB	Output is correct
40	Correct	484 ms	282320 KB	Output is correct
41	Correct	617 ms	282728 KB	Output is correct
42	Correct	501 ms	282956 KB	Output is correct
43	Correct	540 ms	283280 KB	Output is correct
44	Correct	582 ms	283556 KB	Output is correct
45	Correct	619 ms	284004 KB	Output is correct
46	Correct	853 ms	290320 KB	Output is correct
47	Correct	12932 ms	406152 KB	Output is correct
48	Correct	10658 ms	406400 KB	Output is correct
49	Correct	9624 ms	406552 KB	Output is correct
50	Correct	11200 ms	406676 KB	Output is correct
51	Correct	10596 ms	407016 KB	Output is correct
52	Correct	11576 ms	407420 KB	Output is correct
53	Correct	11208 ms	407904 KB	Output is correct
54	Correct	10193 ms	408320 KB	Output is correct
55	Correct	10531 ms	408764 KB	Output is correct
56	Correct	11110 ms	409336 KB	Output is correct
57	Correct	10822 ms	409740 KB	Output is correct
58	Correct	9086 ms	410316 KB	Output is correct
59	Correct	9032 ms	410620 KB	Output is correct
60	Correct	8113 ms	410860 KB	Output is correct
61	Correct	8811 ms	411536 KB	Output is correct
62	Correct	7647 ms	411952 KB	Output is correct
63	Correct	7164 ms	412348 KB	Output is correct
64	Correct	2902 ms	412944 KB	Output is correct
65	Correct	2821 ms	413220 KB	Output is correct
66	Incorrect	217 ms	413220 KB	Output isn't correct
67	Halted	0 ms	0 KB	-

답안 #61745

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 35.0 / 35.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
35.0 / 35.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 38.0