oj.uz

Submission #132264

# Submission time Handle Problem Language Result Execution time Memory
132264 2019-07-18T15:36:04 Z gs14004 Wild Boar (JOI18_wild_boar) C++17
62 / 100
 18000 ms 537324 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
const int MAXL = 100005;
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);
		while(!pq.empty()){
			auto x = pq.top(); pq.pop();
			if(dist[i][x.second] != x.first) 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];
lint dp[MAXL][4];

int main(){
	scanf("%d %d %d %d",&n,&m,&q,&l);
	preprocess();
	for(int i=0; i<l; i++) scanf("%d",&a[i]);
	for(int i=0; i<q; i++){
		int x, v; scanf("%d %d",&x,&v);
		x--;
		a[x] = v;
		memset(dp, 0x3f, sizeof(dp));
		for(int k=0; k<plist[a[0]][a[1]].size(); k++){
			dp[1][k] = plist[a[0]][a[1]][k].cost;
		}
		for(int k=2; k<l; k++){
			for(int x = 0; x < plist[a[k - 2]][a[k - 1]].size(); x++){
				for(int y = 0; y < plist[a[k - 1]][a[k]].size(); y++){
					if(plist[a[k - 2]][a[k - 1]][x].midr != plist[a[k - 1]][a[k]][y].midl){
						dp[k][y] = min(dp[k][y], dp[k - 1][x] + plist[a[k - 1]][a[k]][y].cost);
					}
				}
			}
		}
		int w = plist[a[l - 2]][a[l - 1]].size();
		lint dap = *min_element(dp[l - 1], dp[l - 1] + w);
		if(dap > 9e17) dap = -1;
		printf("%lld\n", dap);
	}
}

Compilation message

wild_boar.cpp: In function 'void preprocess()':
wild_boar.cpp:84:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k = 3; k < pth.size(); k++){
                     ~~^~~~~~~~~~~~
wild_boar.cpp:92:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int x = 0; x < pth.size(); x++){
                     ~~^~~~~~~~~~~~
wild_boar.cpp:96:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int k = x + 1; k < pth.size(); k++){
                           ~~^~~~~~~~~~~~
wild_boar.cpp:107:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int x = 0; x < pth.size(); x++){
                     ~~^~~~~~~~~~~~
wild_boar.cpp:111: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 'int main()':
wild_boar.cpp:140:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0; k<plist[a[0]][a[1]].size(); k++){
                ~^~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:144:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int x = 0; x < plist[a[k - 2]][a[k - 1]].size(); x++){
                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:145:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int y = 0; y < plist[a[k - 1]][a[k]].size(); y++){
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp: In function 'void preprocess()':
wild_boar.cpp:29: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:132: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:134: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:136: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 191 ms 223864 KB Output is correct
2 Correct 190 ms 223868 KB Output is correct
3 Correct 191 ms 223772 KB Output is correct
4 Correct 190 ms 223856 KB Output is correct
5 Correct 192 ms 223848 KB Output is correct
6 Correct 190 ms 223864 KB Output is correct
7 Correct 190 ms 223736 KB Output is correct
8 Correct 191 ms 223732 KB Output is correct
9 Correct 193 ms 223772 KB Output is correct
10 Correct 189 ms 223836 KB Output is correct
11 Correct 190 ms 223812 KB Output is correct
12 Correct 191 ms 223864 KB Output is correct
13 Correct 190 ms 223784 KB Output is correct
14 Correct 193 ms 223864 KB Output is correct
15 Correct 203 ms 223792 KB Output is correct
16 Correct 199 ms 223736 KB Output is correct
17 Correct 194 ms 223864 KB Output is correct
18 Correct 193 ms 223884 KB Output is correct
19 Correct 194 ms 223740 KB Output is correct
20 Correct 191 ms 223932 KB Output is correct
21 Correct 191 ms 223820 KB Output is correct
22 Correct 195 ms 223940 KB Output is correct
23 Correct 189 ms 223752 KB Output is correct
24 Correct 190 ms 223864 KB Output is correct
25 Correct 195 ms 223836 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 223864 KB Output is correct
2 Correct 190 ms 223868 KB Output is correct
3 Correct 191 ms 223772 KB Output is correct
4 Correct 190 ms 223856 KB Output is correct
5 Correct 192 ms 223848 KB Output is correct
6 Correct 190 ms 223864 KB Output is correct
7 Correct 190 ms 223736 KB Output is correct
8 Correct 191 ms 223732 KB Output is correct
9 Correct 193 ms 223772 KB Output is correct
10 Correct 189 ms 223836 KB Output is correct
11 Correct 190 ms 223812 KB Output is correct
12 Correct 191 ms 223864 KB Output is correct
13 Correct 190 ms 223784 KB Output is correct
14 Correct 193 ms 223864 KB Output is correct
15 Correct 203 ms 223792 KB Output is correct
16 Correct 199 ms 223736 KB Output is correct
17 Correct 194 ms 223864 KB Output is correct
18 Correct 193 ms 223884 KB Output is correct
19 Correct 194 ms 223740 KB Output is correct
20 Correct 191 ms 223932 KB Output is correct
21 Correct 191 ms 223820 KB Output is correct
22 Correct 195 ms 223940 KB Output is correct
23 Correct 189 ms 223752 KB Output is correct
24 Correct 190 ms 223864 KB Output is correct
25 Correct 195 ms 223836 KB Output is correct
26 Correct 205 ms 223900 KB Output is correct
27 Correct 212 ms 224928 KB Output is correct
28 Correct 211 ms 224756 KB Output is correct
29 Correct 284 ms 224996 KB Output is correct
30 Correct 279 ms 225144 KB Output is correct
31 Correct 285 ms 225068 KB Output is correct
32 Correct 285 ms 225256 KB Output is correct
33 Correct 283 ms 226044 KB Output is correct
34 Correct 296 ms 226168 KB Output is correct
35 Correct 281 ms 226060 KB Output is correct
36 Correct 288 ms 226140 KB Output is correct
37 Correct 285 ms 226192 KB Output is correct
38 Correct 287 ms 227580 KB Output is correct
39 Correct 323 ms 227576 KB Output is correct
40 Correct 286 ms 227420 KB Output is correct
41 Correct 285 ms 227448 KB Output is correct
42 Correct 272 ms 228656 KB Output is correct
43 Correct 285 ms 229240 KB Output is correct
44 Correct 290 ms 229240 KB Output is correct
45 Correct 263 ms 231288 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 223864 KB Output is correct
2 Correct 190 ms 223868 KB Output is correct
3 Correct 191 ms 223772 KB Output is correct
4 Correct 190 ms 223856 KB Output is correct
5 Correct 192 ms 223848 KB Output is correct
6 Correct 190 ms 223864 KB Output is correct
7 Correct 190 ms 223736 KB Output is correct
8 Correct 191 ms 223732 KB Output is correct
9 Correct 193 ms 223772 KB Output is correct
10 Correct 189 ms 223836 KB Output is correct
11 Correct 190 ms 223812 KB Output is correct
12 Correct 191 ms 223864 KB Output is correct
13 Correct 190 ms 223784 KB Output is correct
14 Correct 193 ms 223864 KB Output is correct
15 Correct 203 ms 223792 KB Output is correct
16 Correct 199 ms 223736 KB Output is correct
17 Correct 194 ms 223864 KB Output is correct
18 Correct 193 ms 223884 KB Output is correct
19 Correct 194 ms 223740 KB Output is correct
20 Correct 191 ms 223932 KB Output is correct
21 Correct 191 ms 223820 KB Output is correct
22 Correct 195 ms 223940 KB Output is correct
23 Correct 189 ms 223752 KB Output is correct
24 Correct 190 ms 223864 KB Output is correct
25 Correct 195 ms 223836 KB Output is correct
26 Correct 205 ms 223900 KB Output is correct
27 Correct 212 ms 224928 KB Output is correct
28 Correct 211 ms 224756 KB Output is correct
29 Correct 284 ms 224996 KB Output is correct
30 Correct 279 ms 225144 KB Output is correct
31 Correct 285 ms 225068 KB Output is correct
32 Correct 285 ms 225256 KB Output is correct
33 Correct 283 ms 226044 KB Output is correct
34 Correct 296 ms 226168 KB Output is correct
35 Correct 281 ms 226060 KB Output is correct
36 Correct 288 ms 226140 KB Output is correct
37 Correct 285 ms 226192 KB Output is correct
38 Correct 287 ms 227580 KB Output is correct
39 Correct 323 ms 227576 KB Output is correct
40 Correct 286 ms 227420 KB Output is correct
41 Correct 285 ms 227448 KB Output is correct
42 Correct 272 ms 228656 KB Output is correct
43 Correct 285 ms 229240 KB Output is correct
44 Correct 290 ms 229240 KB Output is correct
45 Correct 263 ms 231288 KB Output is correct
46 Correct 409 ms 226968 KB Output is correct
47 Correct 6872 ms 244176 KB Output is correct
48 Correct 6190 ms 272052 KB Output is correct
49 Correct 5235 ms 302660 KB Output is correct
50 Correct 5445 ms 302568 KB Output is correct
51 Correct 5973 ms 302796 KB Output is correct
52 Correct 3906 ms 302712 KB Output is correct
53 Correct 3877 ms 302888 KB Output is correct
54 Correct 3860 ms 302672 KB Output is correct
55 Correct 3841 ms 302660 KB Output is correct
56 Correct 3892 ms 319192 KB Output is correct
57 Correct 3902 ms 337128 KB Output is correct
58 Correct 3888 ms 357136 KB Output is correct
59 Correct 3922 ms 377864 KB Output is correct
60 Correct 3885 ms 400804 KB Output is correct
61 Correct 3868 ms 424992 KB Output is correct
62 Correct 3762 ms 450972 KB Output is correct
63 Correct 3661 ms 478200 KB Output is correct
64 Correct 2200 ms 537324 KB Output is correct
65 Correct 2208 ms 537228 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 223864 KB Output is correct
2 Correct 190 ms 223868 KB Output is correct
3 Correct 191 ms 223772 KB Output is correct
4 Correct 190 ms 223856 KB Output is correct
5 Correct 192 ms 223848 KB Output is correct
6 Correct 190 ms 223864 KB Output is correct
7 Correct 190 ms 223736 KB Output is correct
8 Correct 191 ms 223732 KB Output is correct
9 Correct 193 ms 223772 KB Output is correct
10 Correct 189 ms 223836 KB Output is correct
11 Correct 190 ms 223812 KB Output is correct
12 Correct 191 ms 223864 KB Output is correct
13 Correct 190 ms 223784 KB Output is correct
14 Correct 193 ms 223864 KB Output is correct
15 Correct 203 ms 223792 KB Output is correct
16 Correct 199 ms 223736 KB Output is correct
17 Correct 194 ms 223864 KB Output is correct
18 Correct 193 ms 223884 KB Output is correct
19 Correct 194 ms 223740 KB Output is correct
20 Correct 191 ms 223932 KB Output is correct
21 Correct 191 ms 223820 KB Output is correct
22 Correct 195 ms 223940 KB Output is correct
23 Correct 189 ms 223752 KB Output is correct
24 Correct 190 ms 223864 KB Output is correct
25 Correct 195 ms 223836 KB Output is correct
26 Correct 205 ms 223900 KB Output is correct
27 Correct 212 ms 224928 KB Output is correct
28 Correct 211 ms 224756 KB Output is correct
29 Correct 284 ms 224996 KB Output is correct
30 Correct 279 ms 225144 KB Output is correct
31 Correct 285 ms 225068 KB Output is correct
32 Correct 285 ms 225256 KB Output is correct
33 Correct 283 ms 226044 KB Output is correct
34 Correct 296 ms 226168 KB Output is correct
35 Correct 281 ms 226060 KB Output is correct
36 Correct 288 ms 226140 KB Output is correct
37 Correct 285 ms 226192 KB Output is correct
38 Correct 287 ms 227580 KB Output is correct
39 Correct 323 ms 227576 KB Output is correct
40 Correct 286 ms 227420 KB Output is correct
41 Correct 285 ms 227448 KB Output is correct
42 Correct 272 ms 228656 KB Output is correct
43 Correct 285 ms 229240 KB Output is correct
44 Correct 290 ms 229240 KB Output is correct
45 Correct 263 ms 231288 KB Output is correct
46 Correct 409 ms 226968 KB Output is correct
47 Correct 6872 ms 244176 KB Output is correct
48 Correct 6190 ms 272052 KB Output is correct
49 Correct 5235 ms 302660 KB Output is correct
50 Correct 5445 ms 302568 KB Output is correct
51 Correct 5973 ms 302796 KB Output is correct
52 Correct 3906 ms 302712 KB Output is correct
53 Correct 3877 ms 302888 KB Output is correct
54 Correct 3860 ms 302672 KB Output is correct
55 Correct 3841 ms 302660 KB Output is correct
56 Correct 3892 ms 319192 KB Output is correct
57 Correct 3902 ms 337128 KB Output is correct
58 Correct 3888 ms 357136 KB Output is correct
59 Correct 3922 ms 377864 KB Output is correct
60 Correct 3885 ms 400804 KB Output is correct
61 Correct 3868 ms 424992 KB Output is correct
62 Correct 3762 ms 450972 KB Output is correct
63 Correct 3661 ms 478200 KB Output is correct
64 Correct 2200 ms 537324 KB Output is correct
65 Correct 2208 ms 537228 KB Output is correct
66 Correct 981 ms 224240 KB Output is correct
67 Correct 17053 ms 279588 KB Output is correct
68 Correct 2016 ms 445448 KB Output is correct
69 Execution timed out 18126 ms 447568 KB Time limit exceeded
70 Halted 0 ms 0 KB -