답안 #62215 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62215	2018-07-27T21:16:15 Z	cki86201	Wild Boar (JOI18_wild_boar)	C++11	62 / 100	18000 ms	679616 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];

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 > b.Se) a = b;
}

vector <ll> Val[2020][2020];
vector <pii> Idx[2020][2020];

struct node {
	node(){}
	node(int s, int e) {
		V = Val[s][e];
		idx = Idx[s][e];
	}
	vector <ll> V;
	vector <pii> idx;
	ll Get() {
		ll res = 1e18;
		for(ll e : V) res = min(res, e);
		return res;
	}
};

node merge(const node &lhs, const node &rhs) {
	node res;
	int n = szz(lhs.V), m = szz(rhs.V);
	map <pii, ll> Mx;
	rep(i, n) rep(j, m) if(lhs.idx[i].Se != rhs.idx[j].Fi) {
		pii t = pii(lhs.idx[i].Fi, rhs.idx[j].Se);
		ll val = lhs.V[i] + rhs.V[j];
		if(Mx.find(t) == Mx.end() || Mx[t] > val) Mx[t] = val;
	}
	for(auto e : Mx) {
		res.V.pb(e.Se);
		res.idx.pb(e.Fi);
	}
	return res;
}

node Tr[1<<18];

void Init(int rt, int l, int r) {
	if(l == r) {
		Tr[rt] = node(X[l], X[l+1]);
		return;
	}
	int m = (l + r) >> 1;
	Init(rt<<1, l, m);
	Init(rt<<1|1, m+1, r);
	Tr[rt] = merge(Tr[rt<<1], Tr[rt<<1|1]);
}

void update(int rt, int l, int r, int x) {
	if(l == r) {
		Tr[rt] = node(X[l], X[l+1]);
		return;
	}
	int m = (l + r) >> 1;
	if(x <= m) update(rt<<1, l, m, x);
	else update(rt<<1|1, m+1, r, x);
	Tr[rt] = merge(Tr[rt<<1], Tr[rt<<1|1]);
}

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];
	}
	
	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];
		vector <vector <ll> > val;
		rep(a, 4) {
			mn[a].resize(si);
			val.resize(si);
			rep(b, si) mn[a][b].resize(sj), val[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;
				val[k][l] = pp.Fi;
			}
		}
		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 <pii> Sx;
		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]);
			Sx.insert(r.Se);
		}
		rep(k, si) {
			plp r = plp(1e18, pii(-1, -1));
			if(k > 0) updplp(r, mn[0][k-1][sj-1]);
			if(k < si - 1) updplp(r, mn[2][k+1][sj-1]);
			Sx.insert(r.Se);
		}
		rep(l, sj) {
			plp r = plp(1e18, pii(-1, -1));
			if(l > 0) updplp(r, mn[0][si-1][l-1]);
			if(l < sj - 1) updplp(r, mn[1][si-1][l+1]);
			Sx.insert(r.Se);
		}
		plp r = plp(1e18, pii(-1, -1));
		updplp(r, mn[0][si-1][sj-1]);
		Sx.insert(r.Se);
		for(pii e : Sx) if(e.Fi != -1) {
			Idx[i][j].pb(pii(IE[i][e.Fi].Se, IE[j][e.Se].Se));
			ll v = val[e.Fi][e.Se];
			Val[i][j].pb(v);
		}
	}
	
	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);
	}
	
	Init(1, 1, L - 1);
	for(int i=1;i<=T;i++) {
		int x = query[i].Fi;
		int y = query[i].Se;
		X[x] = y;
		if(x > 1) update(1, 1, L - 1, x - 1);
		if(x < L) update(1, 1, L - 1, x);
		ll val = Tr[1].Get();
		if(val >= 1e18) puts("-1");
		else printf("%lld\n", val);
	}

	return 0;
}

Compilation message

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:117: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:120: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:225: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:227: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	245 ms	220920 KB	Output is correct
2	Correct	239 ms	221088 KB	Output is correct
3	Correct	244 ms	221144 KB	Output is correct
4	Correct	239 ms	221300 KB	Output is correct
5	Correct	226 ms	221300 KB	Output is correct
6	Correct	275 ms	221432 KB	Output is correct
7	Correct	217 ms	221432 KB	Output is correct
8	Correct	255 ms	221432 KB	Output is correct
9	Correct	244 ms	221432 KB	Output is correct
10	Correct	201 ms	221432 KB	Output is correct
11	Correct	237 ms	221432 KB	Output is correct
12	Correct	226 ms	221432 KB	Output is correct
13	Correct	194 ms	221432 KB	Output is correct
14	Correct	208 ms	221440 KB	Output is correct
15	Correct	193 ms	221440 KB	Output is correct
16	Correct	197 ms	221440 KB	Output is correct
17	Correct	249 ms	221440 KB	Output is correct
18	Correct	251 ms	221440 KB	Output is correct
19	Correct	232 ms	221456 KB	Output is correct
20	Correct	264 ms	221456 KB	Output is correct
21	Correct	232 ms	221456 KB	Output is correct
22	Correct	228 ms	221456 KB	Output is correct
23	Correct	228 ms	221456 KB	Output is correct
24	Correct	255 ms	221456 KB	Output is correct
25	Correct	201 ms	221456 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	245 ms	220920 KB	Output is correct
2	Correct	239 ms	221088 KB	Output is correct
3	Correct	244 ms	221144 KB	Output is correct
4	Correct	239 ms	221300 KB	Output is correct
5	Correct	226 ms	221300 KB	Output is correct
6	Correct	275 ms	221432 KB	Output is correct
7	Correct	217 ms	221432 KB	Output is correct
8	Correct	255 ms	221432 KB	Output is correct
9	Correct	244 ms	221432 KB	Output is correct
10	Correct	201 ms	221432 KB	Output is correct
11	Correct	237 ms	221432 KB	Output is correct
12	Correct	226 ms	221432 KB	Output is correct
13	Correct	194 ms	221432 KB	Output is correct
14	Correct	208 ms	221440 KB	Output is correct
15	Correct	193 ms	221440 KB	Output is correct
16	Correct	197 ms	221440 KB	Output is correct
17	Correct	249 ms	221440 KB	Output is correct
18	Correct	251 ms	221440 KB	Output is correct
19	Correct	232 ms	221456 KB	Output is correct
20	Correct	264 ms	221456 KB	Output is correct
21	Correct	232 ms	221456 KB	Output is correct
22	Correct	228 ms	221456 KB	Output is correct
23	Correct	228 ms	221456 KB	Output is correct
24	Correct	255 ms	221456 KB	Output is correct
25	Correct	201 ms	221456 KB	Output is correct
26	Correct	197 ms	221620 KB	Output is correct
27	Correct	299 ms	230360 KB	Output is correct
28	Correct	270 ms	230360 KB	Output is correct
29	Correct	714 ms	255908 KB	Output is correct
30	Correct	805 ms	258724 KB	Output is correct
31	Correct	764 ms	259236 KB	Output is correct
32	Correct	849 ms	259236 KB	Output is correct
33	Correct	817 ms	259236 KB	Output is correct
34	Correct	685 ms	259236 KB	Output is correct
35	Correct	618 ms	259364 KB	Output is correct
36	Correct	781 ms	262976 KB	Output is correct
37	Correct	731 ms	262976 KB	Output is correct
38	Correct	728 ms	262976 KB	Output is correct
39	Correct	932 ms	267428 KB	Output is correct
40	Correct	683 ms	267428 KB	Output is correct
41	Correct	631 ms	267428 KB	Output is correct
42	Correct	855 ms	267428 KB	Output is correct
43	Correct	822 ms	267428 KB	Output is correct
44	Correct	659 ms	267428 KB	Output is correct
45	Correct	738 ms	267428 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	245 ms	220920 KB	Output is correct
2	Correct	239 ms	221088 KB	Output is correct
3	Correct	244 ms	221144 KB	Output is correct
4	Correct	239 ms	221300 KB	Output is correct
5	Correct	226 ms	221300 KB	Output is correct
6	Correct	275 ms	221432 KB	Output is correct
7	Correct	217 ms	221432 KB	Output is correct
8	Correct	255 ms	221432 KB	Output is correct
9	Correct	244 ms	221432 KB	Output is correct
10	Correct	201 ms	221432 KB	Output is correct
11	Correct	237 ms	221432 KB	Output is correct
12	Correct	226 ms	221432 KB	Output is correct
13	Correct	194 ms	221432 KB	Output is correct
14	Correct	208 ms	221440 KB	Output is correct
15	Correct	193 ms	221440 KB	Output is correct
16	Correct	197 ms	221440 KB	Output is correct
17	Correct	249 ms	221440 KB	Output is correct
18	Correct	251 ms	221440 KB	Output is correct
19	Correct	232 ms	221456 KB	Output is correct
20	Correct	264 ms	221456 KB	Output is correct
21	Correct	232 ms	221456 KB	Output is correct
22	Correct	228 ms	221456 KB	Output is correct
23	Correct	228 ms	221456 KB	Output is correct
24	Correct	255 ms	221456 KB	Output is correct
25	Correct	201 ms	221456 KB	Output is correct
26	Correct	197 ms	221620 KB	Output is correct
27	Correct	299 ms	230360 KB	Output is correct
28	Correct	270 ms	230360 KB	Output is correct
29	Correct	714 ms	255908 KB	Output is correct
30	Correct	805 ms	258724 KB	Output is correct
31	Correct	764 ms	259236 KB	Output is correct
32	Correct	849 ms	259236 KB	Output is correct
33	Correct	817 ms	259236 KB	Output is correct
34	Correct	685 ms	259236 KB	Output is correct
35	Correct	618 ms	259364 KB	Output is correct
36	Correct	781 ms	262976 KB	Output is correct
37	Correct	731 ms	262976 KB	Output is correct
38	Correct	728 ms	262976 KB	Output is correct
39	Correct	932 ms	267428 KB	Output is correct
40	Correct	683 ms	267428 KB	Output is correct
41	Correct	631 ms	267428 KB	Output is correct
42	Correct	855 ms	267428 KB	Output is correct
43	Correct	822 ms	267428 KB	Output is correct
44	Correct	659 ms	267428 KB	Output is correct
45	Correct	738 ms	267428 KB	Output is correct
46	Correct	1096 ms	267428 KB	Output is correct
47	Correct	13949 ms	404436 KB	Output is correct
48	Correct	13673 ms	439836 KB	Output is correct
49	Correct	13623 ms	477364 KB	Output is correct
50	Correct	13071 ms	477364 KB	Output is correct
51	Correct	12546 ms	477364 KB	Output is correct
52	Correct	14279 ms	477364 KB	Output is correct
53	Correct	15209 ms	477364 KB	Output is correct
54	Correct	14816 ms	477364 KB	Output is correct
55	Correct	14011 ms	477364 KB	Output is correct
56	Correct	14208 ms	490712 KB	Output is correct
57	Correct	14160 ms	512060 KB	Output is correct
58	Correct	13661 ms	535444 KB	Output is correct
59	Correct	12741 ms	560388 KB	Output is correct
60	Correct	12993 ms	587488 KB	Output is correct
61	Correct	15806 ms	616188 KB	Output is correct
62	Correct	15160 ms	646928 KB	Output is correct
63	Correct	13687 ms	679616 KB	Output is correct
64	Correct	9641 ms	679616 KB	Output is correct
65	Correct	9758 ms	679616 KB	Output is correct

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	245 ms	220920 KB	Output is correct
2	Correct	239 ms	221088 KB	Output is correct
3	Correct	244 ms	221144 KB	Output is correct
4	Correct	239 ms	221300 KB	Output is correct
5	Correct	226 ms	221300 KB	Output is correct
6	Correct	275 ms	221432 KB	Output is correct
7	Correct	217 ms	221432 KB	Output is correct
8	Correct	255 ms	221432 KB	Output is correct
9	Correct	244 ms	221432 KB	Output is correct
10	Correct	201 ms	221432 KB	Output is correct
11	Correct	237 ms	221432 KB	Output is correct
12	Correct	226 ms	221432 KB	Output is correct
13	Correct	194 ms	221432 KB	Output is correct
14	Correct	208 ms	221440 KB	Output is correct
15	Correct	193 ms	221440 KB	Output is correct
16	Correct	197 ms	221440 KB	Output is correct
17	Correct	249 ms	221440 KB	Output is correct
18	Correct	251 ms	221440 KB	Output is correct
19	Correct	232 ms	221456 KB	Output is correct
20	Correct	264 ms	221456 KB	Output is correct
21	Correct	232 ms	221456 KB	Output is correct
22	Correct	228 ms	221456 KB	Output is correct
23	Correct	228 ms	221456 KB	Output is correct
24	Correct	255 ms	221456 KB	Output is correct
25	Correct	201 ms	221456 KB	Output is correct
26	Correct	197 ms	221620 KB	Output is correct
27	Correct	299 ms	230360 KB	Output is correct
28	Correct	270 ms	230360 KB	Output is correct
29	Correct	714 ms	255908 KB	Output is correct
30	Correct	805 ms	258724 KB	Output is correct
31	Correct	764 ms	259236 KB	Output is correct
32	Correct	849 ms	259236 KB	Output is correct
33	Correct	817 ms	259236 KB	Output is correct
34	Correct	685 ms	259236 KB	Output is correct
35	Correct	618 ms	259364 KB	Output is correct
36	Correct	781 ms	262976 KB	Output is correct
37	Correct	731 ms	262976 KB	Output is correct
38	Correct	728 ms	262976 KB	Output is correct
39	Correct	932 ms	267428 KB	Output is correct
40	Correct	683 ms	267428 KB	Output is correct
41	Correct	631 ms	267428 KB	Output is correct
42	Correct	855 ms	267428 KB	Output is correct
43	Correct	822 ms	267428 KB	Output is correct
44	Correct	659 ms	267428 KB	Output is correct
45	Correct	738 ms	267428 KB	Output is correct
46	Correct	1096 ms	267428 KB	Output is correct
47	Correct	13949 ms	404436 KB	Output is correct
48	Correct	13673 ms	439836 KB	Output is correct
49	Correct	13623 ms	477364 KB	Output is correct
50	Correct	13071 ms	477364 KB	Output is correct
51	Correct	12546 ms	477364 KB	Output is correct
52	Correct	14279 ms	477364 KB	Output is correct
53	Correct	15209 ms	477364 KB	Output is correct
54	Correct	14816 ms	477364 KB	Output is correct
55	Correct	14011 ms	477364 KB	Output is correct
56	Correct	14208 ms	490712 KB	Output is correct
57	Correct	14160 ms	512060 KB	Output is correct
58	Correct	13661 ms	535444 KB	Output is correct
59	Correct	12741 ms	560388 KB	Output is correct
60	Correct	12993 ms	587488 KB	Output is correct
61	Correct	15806 ms	616188 KB	Output is correct
62	Correct	15160 ms	646928 KB	Output is correct
63	Correct	13687 ms	679616 KB	Output is correct
64	Correct	9641 ms	679616 KB	Output is correct
65	Correct	9758 ms	679616 KB	Output is correct
66	Correct	527 ms	679616 KB	Output is correct
67	Correct	2546 ms	679616 KB	Output is correct
68	Correct	8577 ms	679616 KB	Output is correct
69	Correct	8923 ms	679616 KB	Output is correct
70	Correct	8844 ms	679616 KB	Output is correct
71	Execution timed out	18092 ms	679616 KB	Time limit exceeded
72	Halted	0 ms	0 KB	-

답안 #62215

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