oj.uz

Submission #423884

# Submission time Handle Problem Language Result Execution time Memory
423884 2021-06-11T13:47:28 Z vanic Shortcut (IOI16_shortcut) C++14
0 / 100
 2 ms 460 KB 
#include "shortcut.h"
#include <algorithm>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <set>
#include <cassert>
#include <iostream>

using namespace std;

typedef long long ll;

const int maxn=505;

vector < pair < ll, ll > > ms[maxn];
bitset < maxn > bio;
ll n;
ll br;

ll kreni(ll x){
	set < pair < ll, ll > > s;
	s.insert({0, x});
	pair < ll, ll > p;
	ll zadnj;
	while(!s.empty()){
		p=*s.begin();
		s.erase(s.begin());
//		cout << "a sad je  " << p.second << endl;
		if(bio[p.second]){
//			cout << "cont" << endl;
			continue;
		}
		zadnj=p.first;
		bio[p.second]=1;
		x=p.second;
		for(int i=0; i<(int)ms[x].size(); i++){
			if(!bio[ms[x][i].first]){
//				cout << "sirim " << p.first << ' ' << ms[x][i].second << ' ' << ms[x][i].first  << endl;
				s.insert({p.first+ms[x][i].second, ms[x][i].first});
			}
		}
	}
//	cout << x << ' ' << zadnj << endl;
	return zadnj;
}

ll rijesi(){
	ll sol=0;
	for(int i=0; i<br; i++){
		sol=max(sol, kreni(i));
		bio.reset();
	}
	return sol;
}

ll find_shortcut(int nn, vector < int > l, vector < int > d, int c){
	n=nn;
	assert(n<=10);
	for(int i=0; i<n-1; i++){
		ms[i].push_back({i+1, l[i]});
		ms[i+1].push_back({i, l[i]});
	}
	br=n;
	for(int i=0; i<n; i++){
		if(d[i]){
			ms[br].push_back({i, d[i]});
			ms[i].push_back({br, d[i]});
			br++;
		}
	}
	ll sol=1e18;
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			ms[i].push_back({j, c});
			ms[j].push_back({i, c});
			sol=min(sol, rijesi());
			ms[i].pop_back();
			ms[j].pop_back();
		}
	}
	return sol;
}

Compilation message

shortcut.cpp: In function 'll kreni(ll)':
shortcut.cpp:46:9: warning: 'zadnj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |  return zadnj;
      |         ^~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 0 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 0 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 0 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 204 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 204 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 204 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 204 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 204 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 204 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 204 KB n = 5, 12 is a correct answer
21 Correct 1 ms 204 KB n = 5, 25 is a correct answer
22 Correct 1 ms 204 KB n = 2, 122 is a correct answer
23 Correct 2 ms 204 KB n = 10, 117 is a correct answer
24 Correct 2 ms 204 KB n = 10, 336 is a correct answer
25 Correct 2 ms 204 KB n = 10, 438 is a correct answer
26 Correct 1 ms 204 KB n = 10, 206 is a correct answer
27 Correct 2 ms 204 KB n = 10, 636 is a correct answer
28 Correct 1 ms 204 KB n = 4, 2399 is a correct answer
29 Correct 2 ms 204 KB n = 10, 10992 is a correct answer
30 Correct 2 ms 204 KB n = 10, 3112 is a correct answer
31 Runtime error 1 ms 460 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 0 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 0 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 0 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 204 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 204 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 204 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 204 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 204 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 204 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 204 KB n = 5, 12 is a correct answer
21 Correct 1 ms 204 KB n = 5, 25 is a correct answer
22 Correct 1 ms 204 KB n = 2, 122 is a correct answer
23 Correct 2 ms 204 KB n = 10, 117 is a correct answer
24 Correct 2 ms 204 KB n = 10, 336 is a correct answer
25 Correct 2 ms 204 KB n = 10, 438 is a correct answer
26 Correct 1 ms 204 KB n = 10, 206 is a correct answer
27 Correct 2 ms 204 KB n = 10, 636 is a correct answer
28 Correct 1 ms 204 KB n = 4, 2399 is a correct answer
29 Correct 2 ms 204 KB n = 10, 10992 is a correct answer
30 Correct 2 ms 204 KB n = 10, 3112 is a correct answer
31 Runtime error 1 ms 460 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 0 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 0 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 0 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 204 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 204 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 204 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 204 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 204 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 204 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 204 KB n = 5, 12 is a correct answer
21 Correct 1 ms 204 KB n = 5, 25 is a correct answer
22 Correct 1 ms 204 KB n = 2, 122 is a correct answer
23 Correct 2 ms 204 KB n = 10, 117 is a correct answer
24 Correct 2 ms 204 KB n = 10, 336 is a correct answer
25 Correct 2 ms 204 KB n = 10, 438 is a correct answer
26 Correct 1 ms 204 KB n = 10, 206 is a correct answer
27 Correct 2 ms 204 KB n = 10, 636 is a correct answer
28 Correct 1 ms 204 KB n = 4, 2399 is a correct answer
29 Correct 2 ms 204 KB n = 10, 10992 is a correct answer
30 Correct 2 ms 204 KB n = 10, 3112 is a correct answer
31 Runtime error 1 ms 460 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 0 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 0 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 0 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 204 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 204 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 204 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 204 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 204 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 204 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 204 KB n = 5, 12 is a correct answer
21 Correct 1 ms 204 KB n = 5, 25 is a correct answer
22 Correct 1 ms 204 KB n = 2, 122 is a correct answer
23 Correct 2 ms 204 KB n = 10, 117 is a correct answer
24 Correct 2 ms 204 KB n = 10, 336 is a correct answer
25 Correct 2 ms 204 KB n = 10, 438 is a correct answer
26 Correct 1 ms 204 KB n = 10, 206 is a correct answer
27 Correct 2 ms 204 KB n = 10, 636 is a correct answer
28 Correct 1 ms 204 KB n = 4, 2399 is a correct answer
29 Correct 2 ms 204 KB n = 10, 10992 is a correct answer
30 Correct 2 ms 204 KB n = 10, 3112 is a correct answer
31 Runtime error 1 ms 460 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 0 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 0 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 0 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 204 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 204 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 204 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 204 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 204 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 204 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 204 KB n = 5, 12 is a correct answer
21 Correct 1 ms 204 KB n = 5, 25 is a correct answer
22 Correct 1 ms 204 KB n = 2, 122 is a correct answer
23 Correct 2 ms 204 KB n = 10, 117 is a correct answer
24 Correct 2 ms 204 KB n = 10, 336 is a correct answer
25 Correct 2 ms 204 KB n = 10, 438 is a correct answer
26 Correct 1 ms 204 KB n = 10, 206 is a correct answer
27 Correct 2 ms 204 KB n = 10, 636 is a correct answer
28 Correct 1 ms 204 KB n = 4, 2399 is a correct answer
29 Correct 2 ms 204 KB n = 10, 10992 is a correct answer
30 Correct 2 ms 204 KB n = 10, 3112 is a correct answer
31 Runtime error 1 ms 460 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 0 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 0 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 0 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 204 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 204 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 204 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 204 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 204 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 204 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 204 KB n = 5, 12 is a correct answer
21 Correct 1 ms 204 KB n = 5, 25 is a correct answer
22 Correct 1 ms 204 KB n = 2, 122 is a correct answer
23 Correct 2 ms 204 KB n = 10, 117 is a correct answer
24 Correct 2 ms 204 KB n = 10, 336 is a correct answer
25 Correct 2 ms 204 KB n = 10, 438 is a correct answer
26 Correct 1 ms 204 KB n = 10, 206 is a correct answer
27 Correct 2 ms 204 KB n = 10, 636 is a correct answer
28 Correct 1 ms 204 KB n = 4, 2399 is a correct answer
29 Correct 2 ms 204 KB n = 10, 10992 is a correct answer
30 Correct 2 ms 204 KB n = 10, 3112 is a correct answer
31 Runtime error 1 ms 460 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 0 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 0 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 0 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 204 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 204 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 204 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 204 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 204 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 204 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 204 KB n = 5, 12 is a correct answer
21 Correct 1 ms 204 KB n = 5, 25 is a correct answer
22 Correct 1 ms 204 KB n = 2, 122 is a correct answer
23 Correct 2 ms 204 KB n = 10, 117 is a correct answer
24 Correct 2 ms 204 KB n = 10, 336 is a correct answer
25 Correct 2 ms 204 KB n = 10, 438 is a correct answer
26 Correct 1 ms 204 KB n = 10, 206 is a correct answer
27 Correct 2 ms 204 KB n = 10, 636 is a correct answer
28 Correct 1 ms 204 KB n = 4, 2399 is a correct answer
29 Correct 2 ms 204 KB n = 10, 10992 is a correct answer
30 Correct 2 ms 204 KB n = 10, 3112 is a correct answer
31 Runtime error 1 ms 460 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB n = 4, 80 is a correct answer
2 Correct 1 ms 204 KB n = 9, 110 is a correct answer
3 Correct 0 ms 204 KB n = 4, 21 is a correct answer
4 Correct 1 ms 204 KB n = 3, 4 is a correct answer
5 Correct 1 ms 204 KB n = 2, 62 is a correct answer
6 Correct 1 ms 204 KB n = 2, 3 is a correct answer
7 Correct 0 ms 204 KB n = 3, 29 is a correct answer
8 Correct 1 ms 204 KB n = 2, 3 is a correct answer
9 Correct 0 ms 204 KB n = 2, 3 is a correct answer
10 Correct 1 ms 204 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 204 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 204 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 204 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 204 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 204 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 204 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 204 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 204 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 204 KB n = 5, 12 is a correct answer
21 Correct 1 ms 204 KB n = 5, 25 is a correct answer
22 Correct 1 ms 204 KB n = 2, 122 is a correct answer
23 Correct 2 ms 204 KB n = 10, 117 is a correct answer
24 Correct 2 ms 204 KB n = 10, 336 is a correct answer
25 Correct 2 ms 204 KB n = 10, 438 is a correct answer
26 Correct 1 ms 204 KB n = 10, 206 is a correct answer
27 Correct 2 ms 204 KB n = 10, 636 is a correct answer
28 Correct 1 ms 204 KB n = 4, 2399 is a correct answer
29 Correct 2 ms 204 KB n = 10, 10992 is a correct answer
30 Correct 2 ms 204 KB n = 10, 3112 is a correct answer
31 Runtime error 1 ms 460 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -