답안 #62203 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62203	2018-07-27T20:14:06 Z	cki86201	Wild Boar (JOI18_wild_boar)	C++11	62 / 100	14799 ms	413968 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];

typedef pair<ll, pii> plp;

void updplp(plp &a, plp &b) {
	if(a.Fi > b.Fi) a = b;
	else if(a.Fi == b.Fi) {
		a.Se.Fi = min(a.Se.Fi, b.Se.Fi);
		a.Se.Se = min(a.Se.Se, b.Se.Se);
	}
}

ll Val[2020][2020][4][4];
int Idx_l[2020][2020][4];
int Idx_r[2020][2020][4];

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]);
		vector <vector <plp> > mn[4];
		rep(a, 4) {
			mn[a].resize(si);
			rep(b, si) mn[a][b].resize(sj);
		}
		
		rep(k, si) {
			int eidx = nume[i][k];
			rep(l, sj) {
				int fidx = nume[j][l] ^ 1;
				plp pp = plp(dis[eidx][fidx] + get<2>(edgen[fidx]), pii(k, l));
				rep(t, 4) mn[t][k][l] = pp;
				
				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;
			}
		}
		rep(k, si) for(int l=1;l<sj;l++) for(int a : {0, 2}) updplp(mn[a][k][l], mn[a][k][l-1]);
		rep(k, si) for(int l=sj-2;l>=0;l--) for(int a : {1, 3}) updplp(mn[a][k][l], mn[a][k][l+1]);
		rep(l, sj) for(int k=1;k<si;k++) for(int a : {0, 1}) updplp(mn[a][k][l], mn[a][k-1][l]);
		rep(l, sj) for(int k=si-2;k>=0;k--) for(int a : {2, 3}) updplp(mn[a][k][l], mn[a][k+1][l]);
		set <int> idx_i, idx_j;
		rep(k, si) rep(l, sj) {
			plp r = plp(1e18, pii(-1, -1));
			if(k > 0 && l > 0) updplp(r, mn[0][k-1][l-1]);
			if(k > 0 && l < sj - 1) updplp(r, mn[1][k-1][l+1]);
			if(k < si - 1 && l > 0) updplp(r, mn[2][k+1][l-1]);
			if(k < si - 1 && l < sj - 1) updplp(r, mn[3][k+1][l+1]);
			idx_i.insert(r.Se.Fi);
			idx_j.insert(r.Se.Se);
		}
		if(szz(idx_i) > 4 || szz(idx_j) > 4) {
			return 0;
		}
	}
	
	
	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:68: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:71: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:164: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:166: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	272504 KB	Output is correct
2	Correct	215 ms	272756 KB	Output is correct
3	Correct	212 ms	272892 KB	Output is correct
4	Correct	218 ms	272892 KB	Output is correct
5	Correct	216 ms	272892 KB	Output is correct
6	Correct	217 ms	272892 KB	Output is correct
7	Correct	226 ms	272892 KB	Output is correct
8	Correct	221 ms	272952 KB	Output is correct
9	Correct	211 ms	272952 KB	Output is correct
10	Correct	204 ms	272952 KB	Output is correct
11	Correct	214 ms	272960 KB	Output is correct
12	Correct	204 ms	272960 KB	Output is correct
13	Correct	194 ms	272960 KB	Output is correct
14	Correct	226 ms	273008 KB	Output is correct
15	Correct	249 ms	273008 KB	Output is correct
16	Correct	232 ms	273008 KB	Output is correct
17	Correct	217 ms	273008 KB	Output is correct
18	Correct	200 ms	273008 KB	Output is correct
19	Correct	201 ms	273008 KB	Output is correct
20	Correct	212 ms	273008 KB	Output is correct
21	Correct	222 ms	273168 KB	Output is correct
22	Correct	257 ms	273168 KB	Output is correct
23	Correct	238 ms	273168 KB	Output is correct
24	Correct	216 ms	273168 KB	Output is correct
25	Correct	203 ms	273168 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	209 ms	272504 KB	Output is correct
2	Correct	215 ms	272756 KB	Output is correct
3	Correct	212 ms	272892 KB	Output is correct
4	Correct	218 ms	272892 KB	Output is correct
5	Correct	216 ms	272892 KB	Output is correct
6	Correct	217 ms	272892 KB	Output is correct
7	Correct	226 ms	272892 KB	Output is correct
8	Correct	221 ms	272952 KB	Output is correct
9	Correct	211 ms	272952 KB	Output is correct
10	Correct	204 ms	272952 KB	Output is correct
11	Correct	214 ms	272960 KB	Output is correct
12	Correct	204 ms	272960 KB	Output is correct
13	Correct	194 ms	272960 KB	Output is correct
14	Correct	226 ms	273008 KB	Output is correct
15	Correct	249 ms	273008 KB	Output is correct
16	Correct	232 ms	273008 KB	Output is correct
17	Correct	217 ms	273008 KB	Output is correct
18	Correct	200 ms	273008 KB	Output is correct
19	Correct	201 ms	273008 KB	Output is correct
20	Correct	212 ms	273008 KB	Output is correct
21	Correct	222 ms	273168 KB	Output is correct
22	Correct	257 ms	273168 KB	Output is correct
23	Correct	238 ms	273168 KB	Output is correct
24	Correct	216 ms	273168 KB	Output is correct
25	Correct	203 ms	273168 KB	Output is correct
26	Correct	225 ms	273336 KB	Output is correct
27	Correct	332 ms	274836 KB	Output is correct
28	Correct	335 ms	274968 KB	Output is correct
29	Correct	599 ms	279816 KB	Output is correct
30	Correct	544 ms	279840 KB	Output is correct
31	Correct	601 ms	280112 KB	Output is correct
32	Correct	619 ms	280200 KB	Output is correct
33	Correct	555 ms	280580 KB	Output is correct
34	Correct	572 ms	280796 KB	Output is correct
35	Correct	497 ms	281052 KB	Output is correct
36	Correct	550 ms	281252 KB	Output is correct
37	Correct	637 ms	281652 KB	Output is correct
38	Correct	591 ms	282108 KB	Output is correct
39	Correct	565 ms	282196 KB	Output is correct
40	Correct	603 ms	282416 KB	Output is correct
41	Correct	600 ms	282744 KB	Output is correct
42	Correct	628 ms	283148 KB	Output is correct
43	Correct	617 ms	283356 KB	Output is correct
44	Correct	649 ms	283704 KB	Output is correct
45	Correct	580 ms	284020 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	209 ms	272504 KB	Output is correct
2	Correct	215 ms	272756 KB	Output is correct
3	Correct	212 ms	272892 KB	Output is correct
4	Correct	218 ms	272892 KB	Output is correct
5	Correct	216 ms	272892 KB	Output is correct
6	Correct	217 ms	272892 KB	Output is correct
7	Correct	226 ms	272892 KB	Output is correct
8	Correct	221 ms	272952 KB	Output is correct
9	Correct	211 ms	272952 KB	Output is correct
10	Correct	204 ms	272952 KB	Output is correct
11	Correct	214 ms	272960 KB	Output is correct
12	Correct	204 ms	272960 KB	Output is correct
13	Correct	194 ms	272960 KB	Output is correct
14	Correct	226 ms	273008 KB	Output is correct
15	Correct	249 ms	273008 KB	Output is correct
16	Correct	232 ms	273008 KB	Output is correct
17	Correct	217 ms	273008 KB	Output is correct
18	Correct	200 ms	273008 KB	Output is correct
19	Correct	201 ms	273008 KB	Output is correct
20	Correct	212 ms	273008 KB	Output is correct
21	Correct	222 ms	273168 KB	Output is correct
22	Correct	257 ms	273168 KB	Output is correct
23	Correct	238 ms	273168 KB	Output is correct
24	Correct	216 ms	273168 KB	Output is correct
25	Correct	203 ms	273168 KB	Output is correct
26	Correct	225 ms	273336 KB	Output is correct
27	Correct	332 ms	274836 KB	Output is correct
28	Correct	335 ms	274968 KB	Output is correct
29	Correct	599 ms	279816 KB	Output is correct
30	Correct	544 ms	279840 KB	Output is correct
31	Correct	601 ms	280112 KB	Output is correct
32	Correct	619 ms	280200 KB	Output is correct
33	Correct	555 ms	280580 KB	Output is correct
34	Correct	572 ms	280796 KB	Output is correct
35	Correct	497 ms	281052 KB	Output is correct
36	Correct	550 ms	281252 KB	Output is correct
37	Correct	637 ms	281652 KB	Output is correct
38	Correct	591 ms	282108 KB	Output is correct
39	Correct	565 ms	282196 KB	Output is correct
40	Correct	603 ms	282416 KB	Output is correct
41	Correct	600 ms	282744 KB	Output is correct
42	Correct	628 ms	283148 KB	Output is correct
43	Correct	617 ms	283356 KB	Output is correct
44	Correct	649 ms	283704 KB	Output is correct
45	Correct	580 ms	284020 KB	Output is correct
46	Correct	919 ms	290476 KB	Output is correct
47	Correct	13110 ms	411712 KB	Output is correct
48	Correct	12950 ms	411996 KB	Output is correct
49	Correct	13267 ms	411996 KB	Output is correct
50	Correct	12285 ms	411996 KB	Output is correct
51	Correct	12740 ms	413968 KB	Output is correct
52	Correct	12588 ms	413968 KB	Output is correct
53	Correct	12629 ms	413968 KB	Output is correct
54	Correct	14042 ms	413968 KB	Output is correct
55	Correct	14799 ms	413968 KB	Output is correct
56	Correct	13860 ms	413968 KB	Output is correct
57	Correct	12588 ms	413968 KB	Output is correct
58	Correct	13515 ms	413968 KB	Output is correct
59	Correct	12509 ms	413968 KB	Output is correct
60	Correct	11904 ms	413968 KB	Output is correct
61	Correct	11954 ms	413968 KB	Output is correct
62	Correct	11011 ms	413968 KB	Output is correct
63	Correct	11403 ms	413968 KB	Output is correct
64	Correct	7643 ms	413968 KB	Output is correct
65	Correct	8252 ms	413968 KB	Output is correct

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	209 ms	272504 KB	Output is correct
2	Correct	215 ms	272756 KB	Output is correct
3	Correct	212 ms	272892 KB	Output is correct
4	Correct	218 ms	272892 KB	Output is correct
5	Correct	216 ms	272892 KB	Output is correct
6	Correct	217 ms	272892 KB	Output is correct
7	Correct	226 ms	272892 KB	Output is correct
8	Correct	221 ms	272952 KB	Output is correct
9	Correct	211 ms	272952 KB	Output is correct
10	Correct	204 ms	272952 KB	Output is correct
11	Correct	214 ms	272960 KB	Output is correct
12	Correct	204 ms	272960 KB	Output is correct
13	Correct	194 ms	272960 KB	Output is correct
14	Correct	226 ms	273008 KB	Output is correct
15	Correct	249 ms	273008 KB	Output is correct
16	Correct	232 ms	273008 KB	Output is correct
17	Correct	217 ms	273008 KB	Output is correct
18	Correct	200 ms	273008 KB	Output is correct
19	Correct	201 ms	273008 KB	Output is correct
20	Correct	212 ms	273008 KB	Output is correct
21	Correct	222 ms	273168 KB	Output is correct
22	Correct	257 ms	273168 KB	Output is correct
23	Correct	238 ms	273168 KB	Output is correct
24	Correct	216 ms	273168 KB	Output is correct
25	Correct	203 ms	273168 KB	Output is correct
26	Correct	225 ms	273336 KB	Output is correct
27	Correct	332 ms	274836 KB	Output is correct
28	Correct	335 ms	274968 KB	Output is correct
29	Correct	599 ms	279816 KB	Output is correct
30	Correct	544 ms	279840 KB	Output is correct
31	Correct	601 ms	280112 KB	Output is correct
32	Correct	619 ms	280200 KB	Output is correct
33	Correct	555 ms	280580 KB	Output is correct
34	Correct	572 ms	280796 KB	Output is correct
35	Correct	497 ms	281052 KB	Output is correct
36	Correct	550 ms	281252 KB	Output is correct
37	Correct	637 ms	281652 KB	Output is correct
38	Correct	591 ms	282108 KB	Output is correct
39	Correct	565 ms	282196 KB	Output is correct
40	Correct	603 ms	282416 KB	Output is correct
41	Correct	600 ms	282744 KB	Output is correct
42	Correct	628 ms	283148 KB	Output is correct
43	Correct	617 ms	283356 KB	Output is correct
44	Correct	649 ms	283704 KB	Output is correct
45	Correct	580 ms	284020 KB	Output is correct
46	Correct	919 ms	290476 KB	Output is correct
47	Correct	13110 ms	411712 KB	Output is correct
48	Correct	12950 ms	411996 KB	Output is correct
49	Correct	13267 ms	411996 KB	Output is correct
50	Correct	12285 ms	411996 KB	Output is correct
51	Correct	12740 ms	413968 KB	Output is correct
52	Correct	12588 ms	413968 KB	Output is correct
53	Correct	12629 ms	413968 KB	Output is correct
54	Correct	14042 ms	413968 KB	Output is correct
55	Correct	14799 ms	413968 KB	Output is correct
56	Correct	13860 ms	413968 KB	Output is correct
57	Correct	12588 ms	413968 KB	Output is correct
58	Correct	13515 ms	413968 KB	Output is correct
59	Correct	12509 ms	413968 KB	Output is correct
60	Correct	11904 ms	413968 KB	Output is correct
61	Correct	11954 ms	413968 KB	Output is correct
62	Correct	11011 ms	413968 KB	Output is correct
63	Correct	11403 ms	413968 KB	Output is correct
64	Correct	7643 ms	413968 KB	Output is correct
65	Correct	8252 ms	413968 KB	Output is correct
66	Incorrect	245 ms	413968 KB	Output isn't correct
67	Halted	0 ms	0 KB	-

답안 #62203

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