oj.uz

Submission #132273

# Submission time Handle Problem Language Result Execution time Memory
132273 2019-07-18T16:05:18 Z gs14004 Wild Boar (JOI18_wild_boar) C++17
100 / 100
 7147 ms 567428 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
const int MAXL = 100005;
const int MAXT = 270000;
using lint = long long;
using pi = pair<lint, int>;

struct edg{
	int pos, idx, cost;
};

int n, m, q, l;
vector<edg> gph[MAXN];
lint dist[MAXN * 2][MAXN * 2];

struct path_info{
	int midl, midr;
	lint cost;
	bool operator<(const path_info &p)const{
		return cost < p.cost;
	}
};

vector<path_info> plist[MAXN][MAXN];
int ed[MAXN * 2], cost[MAXN * 2];

void preprocess(){
	for(int i=0; i<m; i++){
		int s, e, x; scanf("%d %d %d",&s,&e,&x);
		ed[2 * i] = e; ed[2 * i + 1] = s;
		cost[2 * i] = cost[2 * i + 1] = x;
		gph[s].push_back({e, i*2, x});
		gph[e].push_back({s, i*2+1, x});
	}
	memset(dist, 0x3f, sizeof(dist));
	for(int i=0; i<2*m; i++){
		dist[i][i] = cost[i];
		priority_queue<pi, vector<pi>, greater<pi> > pq;
		pq.emplace(cost[i], i);
		int vis[MAXN] = {};
		while(!pq.empty()){
			auto x = pq.top(); pq.pop();
			if(dist[i][x.second] != x.first) continue;
			vis[ed[x.second]]++;
			if(vis[ed[x.second]] > 2) continue;
			for(auto &j : gph[ed[x.second]]){
				if((j.idx ^ x.second) == 1) continue;
				if(dist[i][j.idx] > x.first + j.cost){
					dist[i][j.idx] = x.first + j.cost;
					pq.emplace(dist[i][j.idx], j.idx);
				}
			}
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(i != j){
				vector<path_info> pth;
				for(auto &k : gph[i]){
					for(auto &l : gph[j]){
						lint cost = dist[k.idx][l.idx ^ 1];
						pth.push_back({k.pos, l.pos, cost});
					}
				}
				sort(pth.begin(), pth.end());
				if(pth.size() <= 2){
					plist[i][j] = pth;
					continue;
				}
				plist[i][j].push_back(pth[0]);
				plist[i][j].push_back(pth[1]);
				if(pth[0].midl != pth[1].midl && pth[0].midr != pth[1].midr){
					plist[i][j].push_back(pth[2]);
					pi nxt_punkty = pi(-1, -1);
					if(pth[2].midl == pth[1].midl){
						nxt_punkty = pi(pth[2].midl, pth[0].midr);
					}
					else if(pth[2].midl == pth[0].midl){
						nxt_punkty = pi(pth[2].midl, pth[1].midr);
					}
					else if(pth[2].midr == pth[1].midr){
						nxt_punkty = pi(pth[0].midl, pth[2].midr);
					}
					else if(pth[2].midr == pth[0].midr){
						nxt_punkty = pi(pth[1].midl, pth[2].midr);
					}
					for(int k = 3; k < pth.size(); k++){
						if(nxt_punkty.first != pth[k].midl && nxt_punkty.second != pth[k].midr){
							plist[i][j].push_back(pth[k]);
							break;
						}
					}
				}
				else if(pth[0].midl == pth[1].midl){
					for(int x = 0; x < pth.size(); x++){
						if(pth[x].midl != pth[0].midl){
							plist[i][j].push_back(pth[x]);
							pi nxt_punkty = pi(pth[0].midl, pth[x].midr);
							for(int k = x + 1; k < pth.size(); k++){
								if(nxt_punkty.first != pth[k].midl && nxt_punkty.second != pth[k].midr){
									plist[i][j].push_back(pth[k]);
									break;
								}
							}
							break;
						}
					}
				}
				else if(pth[0].midr == pth[1].midr){
					for(int x = 0; x < pth.size(); x++){
						if(pth[x].midr != pth[0].midr){
							plist[i][j].push_back(pth[x]);
							pi nxt_punkty = pi(pth[x].midl, pth[0].midr);
							for(int k = x + 1; k < pth.size(); k++){
								if(nxt_punkty.first != pth[k].midl && nxt_punkty.second != pth[k].midr){
									plist[i][j].push_back(pth[k]);
									break;
								}
							}
							break;
						}
					}
				}
				else assert(0);
			//	for(auto &k : plist[i][j]) printf("(%d -> %d), (%d -> %d), %lld\n", i, k.midl, k.midr, j, k.cost);
			}
		}
	}
}

int a[MAXL], lim;
struct seg{
	int l[4], r[4];
	lint cost[4][4];
}tree[MAXT];

seg merge(seg &a, seg &b){
	seg c;
	for(int i=0; i<4; i++){
		c.l[i] = a.l[i];
		c.r[i] = b.r[i];
	}
	memset(c.cost, 0x3f, sizeof(c.cost));
	for(int i=0; i<4; i++){
		for(int j=0; j<4; j++){
			for(int k=0; k<4; k++){
				for(int l=0; l<4; l++){
					if(!a.r[k] || !b.l[i] || a.r[k] != b.l[l]) c.cost[i][j] = min(c.cost[i][j], a.cost[i][k] + b.cost[l][j]);
				}
			}
		}
	}
	return c;
}

void upd(int v){
	memset(tree[v + lim].cost, 0x3f, sizeof(tree[v + lim].cost));
	for(int i=0; i<plist[a[v-1]][a[v]].size(); i++){
		tree[v + lim].l[i] = plist[a[v-1]][a[v]][i].midl;
		tree[v + lim].r[i] = plist[a[v-1]][a[v]][i].midr;
		tree[v + lim].cost[i][i] = plist[a[v-1]][a[v]][i].cost;
	}
	v += lim;
	while(v > 1){
		v >>= 1;
		tree[v] = merge(tree[2*v], tree[2*v+1]);
	}
}

int main(){
	scanf("%d %d %d %d",&n,&m,&q,&l);
	preprocess();
	for(int i=0; i<l; i++) scanf("%d",&a[i]);
	for(lim = 1; lim <= l; lim <<= 1);
	for(int i=1; i<l; i++) upd(i);
	for(int i=0; i<q; i++){
		int x, v; scanf("%d %d",&x,&v);
		x--;
		a[x] = v;
		if(x > 0) upd(x);
		if(x + 1 < l) upd(x + 1);
		lint ret = 1e18;
		for(int j=0; j<4; j++){
			for(int k=0; k<4; k++) ret = min(ret, tree[1].cost[j][k]);
		}
		if(ret > 9e17) ret = -1;
		printf("%lld\n", ret);
	}
}

Compilation message

wild_boar.cpp: In function 'void preprocess()':
wild_boar.cpp:88:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k = 3; k < pth.size(); k++){
                     ~~^~~~~~~~~~~~
wild_boar.cpp:96:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int x = 0; x < pth.size(); x++){
                     ~~^~~~~~~~~~~~
wild_boar.cpp:100:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int k = x + 1; k < pth.size(); k++){
                           ~~^~~~~~~~~~~~
wild_boar.cpp:111:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int x = 0; x < pth.size(); x++){
                     ~~^~~~~~~~~~~~
wild_boar.cpp:115:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int k = x + 1; k < pth.size(); k++){
                           ~~^~~~~~~~~~~~
wild_boar.cpp: In function 'void upd(int)':
wild_boar.cpp:159:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<plist[a[v-1]][a[v]].size(); i++){
               ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp: In function 'void preprocess()':
wild_boar.cpp:30:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, e, x; scanf("%d %d %d",&s,&e,&x);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:172: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,&q,&l);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:174:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<l; i++) scanf("%d",&a[i]);
                         ~~~~~^~~~~~~~~~~~
wild_boar.cpp:178:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, v; scanf("%d %d",&x,&v);
             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 220764 KB Output is correct
2 Correct 188 ms 220920 KB Output is correct
3 Correct 188 ms 220664 KB Output is correct
4 Correct 198 ms 220920 KB Output is correct
5 Correct 193 ms 220668 KB Output is correct
6 Correct 191 ms 220664 KB Output is correct
7 Correct 186 ms 220664 KB Output is correct
8 Correct 187 ms 220620 KB Output is correct
9 Correct 188 ms 220780 KB Output is correct
10 Correct 189 ms 220644 KB Output is correct
11 Correct 193 ms 220676 KB Output is correct
12 Correct 208 ms 220672 KB Output is correct
13 Correct 188 ms 220780 KB Output is correct
14 Correct 191 ms 220664 KB Output is correct
15 Correct 189 ms 220736 KB Output is correct
16 Correct 188 ms 220636 KB Output is correct
17 Correct 187 ms 220652 KB Output is correct
18 Correct 188 ms 220620 KB Output is correct
19 Correct 186 ms 220664 KB Output is correct
20 Correct 186 ms 220644 KB Output is correct
21 Correct 186 ms 220664 KB Output is correct
22 Correct 186 ms 220604 KB Output is correct
23 Correct 187 ms 220652 KB Output is correct
24 Correct 195 ms 220700 KB Output is correct
25 Correct 190 ms 220668 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 220764 KB Output is correct
2 Correct 188 ms 220920 KB Output is correct
3 Correct 188 ms 220664 KB Output is correct
4 Correct 198 ms 220920 KB Output is correct
5 Correct 193 ms 220668 KB Output is correct
6 Correct 191 ms 220664 KB Output is correct
7 Correct 186 ms 220664 KB Output is correct
8 Correct 187 ms 220620 KB Output is correct
9 Correct 188 ms 220780 KB Output is correct
10 Correct 189 ms 220644 KB Output is correct
11 Correct 193 ms 220676 KB Output is correct
12 Correct 208 ms 220672 KB Output is correct
13 Correct 188 ms 220780 KB Output is correct
14 Correct 191 ms 220664 KB Output is correct
15 Correct 189 ms 220736 KB Output is correct
16 Correct 188 ms 220636 KB Output is correct
17 Correct 187 ms 220652 KB Output is correct
18 Correct 188 ms 220620 KB Output is correct
19 Correct 186 ms 220664 KB Output is correct
20 Correct 186 ms 220644 KB Output is correct
21 Correct 186 ms 220664 KB Output is correct
22 Correct 186 ms 220604 KB Output is correct
23 Correct 187 ms 220652 KB Output is correct
24 Correct 195 ms 220700 KB Output is correct
25 Correct 190 ms 220668 KB Output is correct
26 Correct 189 ms 220744 KB Output is correct
27 Correct 1244 ms 253232 KB Output is correct
28 Correct 1267 ms 253032 KB Output is correct
29 Correct 1306 ms 253276 KB Output is correct
30 Correct 1301 ms 253344 KB Output is correct
31 Correct 1283 ms 253364 KB Output is correct
32 Correct 1255 ms 253352 KB Output is correct
33 Correct 1309 ms 254392 KB Output is correct
34 Correct 1316 ms 254360 KB Output is correct
35 Correct 1284 ms 254472 KB Output is correct
36 Correct 1383 ms 254344 KB Output is correct
37 Correct 1318 ms 254200 KB Output is correct
38 Correct 1296 ms 255736 KB Output is correct
39 Correct 1278 ms 255620 KB Output is correct
40 Correct 1303 ms 255680 KB Output is correct
41 Correct 1301 ms 255752 KB Output is correct
42 Correct 1261 ms 256736 KB Output is correct
43 Correct 1288 ms 257392 KB Output is correct
44 Correct 1292 ms 257448 KB Output is correct
45 Correct 1275 ms 259488 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 220764 KB Output is correct
2 Correct 188 ms 220920 KB Output is correct
3 Correct 188 ms 220664 KB Output is correct
4 Correct 198 ms 220920 KB Output is correct
5 Correct 193 ms 220668 KB Output is correct
6 Correct 191 ms 220664 KB Output is correct
7 Correct 186 ms 220664 KB Output is correct
8 Correct 187 ms 220620 KB Output is correct
9 Correct 188 ms 220780 KB Output is correct
10 Correct 189 ms 220644 KB Output is correct
11 Correct 193 ms 220676 KB Output is correct
12 Correct 208 ms 220672 KB Output is correct
13 Correct 188 ms 220780 KB Output is correct
14 Correct 191 ms 220664 KB Output is correct
15 Correct 189 ms 220736 KB Output is correct
16 Correct 188 ms 220636 KB Output is correct
17 Correct 187 ms 220652 KB Output is correct
18 Correct 188 ms 220620 KB Output is correct
19 Correct 186 ms 220664 KB Output is correct
20 Correct 186 ms 220644 KB Output is correct
21 Correct 186 ms 220664 KB Output is correct
22 Correct 186 ms 220604 KB Output is correct
23 Correct 187 ms 220652 KB Output is correct
24 Correct 195 ms 220700 KB Output is correct
25 Correct 190 ms 220668 KB Output is correct
26 Correct 189 ms 220744 KB Output is correct
27 Correct 1244 ms 253232 KB Output is correct
28 Correct 1267 ms 253032 KB Output is correct
29 Correct 1306 ms 253276 KB Output is correct
30 Correct 1301 ms 253344 KB Output is correct
31 Correct 1283 ms 253364 KB Output is correct
32 Correct 1255 ms 253352 KB Output is correct
33 Correct 1309 ms 254392 KB Output is correct
34 Correct 1316 ms 254360 KB Output is correct
35 Correct 1284 ms 254472 KB Output is correct
36 Correct 1383 ms 254344 KB Output is correct
37 Correct 1318 ms 254200 KB Output is correct
38 Correct 1296 ms 255736 KB Output is correct
39 Correct 1278 ms 255620 KB Output is correct
40 Correct 1303 ms 255680 KB Output is correct
41 Correct 1301 ms 255752 KB Output is correct
42 Correct 1261 ms 256736 KB Output is correct
43 Correct 1288 ms 257392 KB Output is correct
44 Correct 1292 ms 257448 KB Output is correct
45 Correct 1275 ms 259488 KB Output is correct
46 Correct 386 ms 223824 KB Output is correct
47 Correct 4584 ms 272008 KB Output is correct
48 Correct 4536 ms 300232 KB Output is correct
49 Correct 4610 ms 330868 KB Output is correct
50 Correct 4638 ms 330824 KB Output is correct
51 Correct 4564 ms 330788 KB Output is correct
52 Correct 4592 ms 330824 KB Output is correct
53 Correct 4597 ms 330916 KB Output is correct
54 Correct 4580 ms 330816 KB Output is correct
55 Correct 4653 ms 330876 KB Output is correct
56 Correct 4631 ms 347288 KB Output is correct
57 Correct 4669 ms 365284 KB Output is correct
58 Correct 4728 ms 384912 KB Output is correct
59 Correct 4723 ms 406044 KB Output is correct
60 Correct 4757 ms 428720 KB Output is correct
61 Correct 4757 ms 452856 KB Output is correct
62 Correct 4715 ms 478680 KB Output is correct
63 Correct 4641 ms 506064 KB Output is correct
64 Correct 3213 ms 565552 KB Output is correct
65 Correct 3216 ms 565708 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 220764 KB Output is correct
2 Correct 188 ms 220920 KB Output is correct
3 Correct 188 ms 220664 KB Output is correct
4 Correct 198 ms 220920 KB Output is correct
5 Correct 193 ms 220668 KB Output is correct
6 Correct 191 ms 220664 KB Output is correct
7 Correct 186 ms 220664 KB Output is correct
8 Correct 187 ms 220620 KB Output is correct
9 Correct 188 ms 220780 KB Output is correct
10 Correct 189 ms 220644 KB Output is correct
11 Correct 193 ms 220676 KB Output is correct
12 Correct 208 ms 220672 KB Output is correct
13 Correct 188 ms 220780 KB Output is correct
14 Correct 191 ms 220664 KB Output is correct
15 Correct 189 ms 220736 KB Output is correct
16 Correct 188 ms 220636 KB Output is correct
17 Correct 187 ms 220652 KB Output is correct
18 Correct 188 ms 220620 KB Output is correct
19 Correct 186 ms 220664 KB Output is correct
20 Correct 186 ms 220644 KB Output is correct
21 Correct 186 ms 220664 KB Output is correct
22 Correct 186 ms 220604 KB Output is correct
23 Correct 187 ms 220652 KB Output is correct
24 Correct 195 ms 220700 KB Output is correct
25 Correct 190 ms 220668 KB Output is correct
26 Correct 189 ms 220744 KB Output is correct
27 Correct 1244 ms 253232 KB Output is correct
28 Correct 1267 ms 253032 KB Output is correct
29 Correct 1306 ms 253276 KB Output is correct
30 Correct 1301 ms 253344 KB Output is correct
31 Correct 1283 ms 253364 KB Output is correct
32 Correct 1255 ms 253352 KB Output is correct
33 Correct 1309 ms 254392 KB Output is correct
34 Correct 1316 ms 254360 KB Output is correct
35 Correct 1284 ms 254472 KB Output is correct
36 Correct 1383 ms 254344 KB Output is correct
37 Correct 1318 ms 254200 KB Output is correct
38 Correct 1296 ms 255736 KB Output is correct
39 Correct 1278 ms 255620 KB Output is correct
40 Correct 1303 ms 255680 KB Output is correct
41 Correct 1301 ms 255752 KB Output is correct
42 Correct 1261 ms 256736 KB Output is correct
43 Correct 1288 ms 257392 KB Output is correct
44 Correct 1292 ms 257448 KB Output is correct
45 Correct 1275 ms 259488 KB Output is correct
46 Correct 386 ms 223824 KB Output is correct
47 Correct 4584 ms 272008 KB Output is correct
48 Correct 4536 ms 300232 KB Output is correct
49 Correct 4610 ms 330868 KB Output is correct
50 Correct 4638 ms 330824 KB Output is correct
51 Correct 4564 ms 330788 KB Output is correct
52 Correct 4592 ms 330824 KB Output is correct
53 Correct 4597 ms 330916 KB Output is correct
54 Correct 4580 ms 330816 KB Output is correct
55 Correct 4653 ms 330876 KB Output is correct
56 Correct 4631 ms 347288 KB Output is correct
57 Correct 4669 ms 365284 KB Output is correct
58 Correct 4728 ms 384912 KB Output is correct
59 Correct 4723 ms 406044 KB Output is correct
60 Correct 4757 ms 428720 KB Output is correct
61 Correct 4757 ms 452856 KB Output is correct
62 Correct 4715 ms 478680 KB Output is correct
63 Correct 4641 ms 506064 KB Output is correct
64 Correct 3213 ms 565552 KB Output is correct
65 Correct 3216 ms 565708 KB Output is correct
66 Correct 1231 ms 252676 KB Output is correct
67 Correct 1518 ms 276328 KB Output is correct
68 Correct 2021 ms 442596 KB Output is correct
69 Correct 2940 ms 444252 KB Output is correct
70 Correct 5371 ms 474972 KB Output is correct
71 Correct 6793 ms 273884 KB Output is correct
72 Correct 6746 ms 304192 KB Output is correct
73 Correct 7138 ms 332592 KB Output is correct
74 Correct 7108 ms 332720 KB Output is correct
75 Correct 7046 ms 332544 KB Output is correct
76 Correct 6853 ms 332512 KB Output is correct
77 Correct 6647 ms 332404 KB Output is correct
78 Correct 6524 ms 332248 KB Output is correct
79 Correct 7078 ms 367012 KB Output is correct
80 Correct 7147 ms 386548 KB Output is correct
81 Correct 6679 ms 407484 KB Output is correct
82 Correct 7063 ms 430404 KB Output is correct
83 Correct 6763 ms 454576 KB Output is correct
84 Correct 6881 ms 507876 KB Output is correct
85 Correct 5279 ms 567428 KB Output is correct