답안 #61738 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61738	2018-07-26T13:40:09 Z	cki86201	Wild Boar (JOI18_wild_boar)	C++11	12 / 100	282 ms	273272 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<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] < 1e17) {
			int eidx = edgec[pre][j];
			rep(u, 2) if(tmn[eidx][nxt][u].Fi < 1e17) {
				int fj = (int)tmn[eidx][nxt][u].Se;
				tdp[fj] = min(tdp[fj], dp[j] + tmn[eidx][nxt][u].Fi);
			}
		}
		for(int j=1;j<=N;j++) if(edgec[j][nxt] != -1) {
			tdp[j] += get<2>(edgen[edgec[j][nxt]]);
		}
		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 > 1e17) 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	254 ms	272716 KB	Output is correct
2	Correct	231 ms	272764 KB	Output is correct
3	Correct	260 ms	272764 KB	Output is correct
4	Correct	218 ms	272764 KB	Output is correct
5	Correct	206 ms	272764 KB	Output is correct
6	Correct	260 ms	272764 KB	Output is correct
7	Correct	257 ms	272776 KB	Output is correct
8	Correct	210 ms	272776 KB	Output is correct
9	Correct	214 ms	272776 KB	Output is correct
10	Correct	231 ms	272940 KB	Output is correct
11	Correct	238 ms	272940 KB	Output is correct
12	Correct	237 ms	272940 KB	Output is correct
13	Correct	244 ms	272940 KB	Output is correct
14	Correct	282 ms	272940 KB	Output is correct
15	Correct	222 ms	272944 KB	Output is correct
16	Correct	203 ms	272952 KB	Output is correct
17	Correct	230 ms	272964 KB	Output is correct
18	Correct	195 ms	272964 KB	Output is correct
19	Correct	210 ms	272964 KB	Output is correct
20	Correct	200 ms	272988 KB	Output is correct
21	Correct	201 ms	273004 KB	Output is correct
22	Correct	245 ms	273004 KB	Output is correct
23	Correct	223 ms	273004 KB	Output is correct
24	Correct	230 ms	273012 KB	Output is correct
25	Correct	250 ms	273012 KB	Output is correct

Subtask #2
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	254 ms	272716 KB	Output is correct
2	Correct	231 ms	272764 KB	Output is correct
3	Correct	260 ms	272764 KB	Output is correct
4	Correct	218 ms	272764 KB	Output is correct
5	Correct	206 ms	272764 KB	Output is correct
6	Correct	260 ms	272764 KB	Output is correct
7	Correct	257 ms	272776 KB	Output is correct
8	Correct	210 ms	272776 KB	Output is correct
9	Correct	214 ms	272776 KB	Output is correct
10	Correct	231 ms	272940 KB	Output is correct
11	Correct	238 ms	272940 KB	Output is correct
12	Correct	237 ms	272940 KB	Output is correct
13	Correct	244 ms	272940 KB	Output is correct
14	Correct	282 ms	272940 KB	Output is correct
15	Correct	222 ms	272944 KB	Output is correct
16	Correct	203 ms	272952 KB	Output is correct
17	Correct	230 ms	272964 KB	Output is correct
18	Correct	195 ms	272964 KB	Output is correct
19	Correct	210 ms	272964 KB	Output is correct
20	Correct	200 ms	272988 KB	Output is correct
21	Correct	201 ms	273004 KB	Output is correct
22	Correct	245 ms	273004 KB	Output is correct
23	Correct	223 ms	273004 KB	Output is correct
24	Correct	230 ms	273012 KB	Output is correct
25	Correct	250 ms	273012 KB	Output is correct
26	Incorrect	247 ms	273272 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	254 ms	272716 KB	Output is correct
2	Correct	231 ms	272764 KB	Output is correct
3	Correct	260 ms	272764 KB	Output is correct
4	Correct	218 ms	272764 KB	Output is correct
5	Correct	206 ms	272764 KB	Output is correct
6	Correct	260 ms	272764 KB	Output is correct
7	Correct	257 ms	272776 KB	Output is correct
8	Correct	210 ms	272776 KB	Output is correct
9	Correct	214 ms	272776 KB	Output is correct
10	Correct	231 ms	272940 KB	Output is correct
11	Correct	238 ms	272940 KB	Output is correct
12	Correct	237 ms	272940 KB	Output is correct
13	Correct	244 ms	272940 KB	Output is correct
14	Correct	282 ms	272940 KB	Output is correct
15	Correct	222 ms	272944 KB	Output is correct
16	Correct	203 ms	272952 KB	Output is correct
17	Correct	230 ms	272964 KB	Output is correct
18	Correct	195 ms	272964 KB	Output is correct
19	Correct	210 ms	272964 KB	Output is correct
20	Correct	200 ms	272988 KB	Output is correct
21	Correct	201 ms	273004 KB	Output is correct
22	Correct	245 ms	273004 KB	Output is correct
23	Correct	223 ms	273004 KB	Output is correct
24	Correct	230 ms	273012 KB	Output is correct
25	Correct	250 ms	273012 KB	Output is correct
26	Incorrect	247 ms	273272 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	254 ms	272716 KB	Output is correct
2	Correct	231 ms	272764 KB	Output is correct
3	Correct	260 ms	272764 KB	Output is correct
4	Correct	218 ms	272764 KB	Output is correct
5	Correct	206 ms	272764 KB	Output is correct
6	Correct	260 ms	272764 KB	Output is correct
7	Correct	257 ms	272776 KB	Output is correct
8	Correct	210 ms	272776 KB	Output is correct
9	Correct	214 ms	272776 KB	Output is correct
10	Correct	231 ms	272940 KB	Output is correct
11	Correct	238 ms	272940 KB	Output is correct
12	Correct	237 ms	272940 KB	Output is correct
13	Correct	244 ms	272940 KB	Output is correct
14	Correct	282 ms	272940 KB	Output is correct
15	Correct	222 ms	272944 KB	Output is correct
16	Correct	203 ms	272952 KB	Output is correct
17	Correct	230 ms	272964 KB	Output is correct
18	Correct	195 ms	272964 KB	Output is correct
19	Correct	210 ms	272964 KB	Output is correct
20	Correct	200 ms	272988 KB	Output is correct
21	Correct	201 ms	273004 KB	Output is correct
22	Correct	245 ms	273004 KB	Output is correct
23	Correct	223 ms	273004 KB	Output is correct
24	Correct	230 ms	273012 KB	Output is correct
25	Correct	250 ms	273012 KB	Output is correct
26	Incorrect	247 ms	273272 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

답안 #61738

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 35.0

Subtask #3 0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 35.0

Subtask #3
0 / 15.0

Subtask #4
0 / 38.0