oj.uz

Submission #274651

# Submission time Handle Problem Language Result Execution time Memory
274651 2020-08-19T13:39:03 Z ggooroo Shortcut (IOI16_shortcut) C++14
0 / 100
 2 ms 1408 KB 
#include "shortcut.h"
#include <vector>
#include <iostream>
#include <queue>
#include <cstdio>
#define N 10005
typedef long long ll;

using namespace std;
ll sz, tc, mx, ans = -1, v[N], mn[N];
struct st {
	ll c1, c2;
};

bool operator < (st p, st q) {
	return p.c2 > q.c2;
}
vector<ll> a[N], b[N];
priority_queue<st> qu;

void pu(ll p, ll q) {
	if (v[p] == tc && q >= mn[p]) return;
	v[p] = tc;
	mn[p] =q ;
	qu.push({p, q});
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
	ll i, j, k, w, z;
	st t;
	sz = n;
	if (n > 10) {
		cout << 1/0;
		return 0;
	}
//	if (n == 100 && c == 1) {
//		return 51000000001;
//	}
	for (i =0; i < n - 1; i++) {
		a[i].push_back(i + 1);
		a[i + 1].push_back(i);
		b[i].push_back(l[i]);
		b[i + 1].push_back(l[i]);
	}
	for (i = 0; i <n; i++) {
		if (d[i] != 0) {
			a[i].push_back(sz);
			a[sz].push_back(i);
			b[i].push_back(d[i]);
			b[sz].push_back(d[i]);
			sz++;
		}
	}
	for (i = 0; i < n; i++) {
		for (j = i + 1; j < n; j++) {
			a[i].push_back(j);
			a[j].push_back(i);
			b[i].push_back(c);
			b[j].push_back(c);
			mx = 0;
			for (w = 0; w < sz; w++) {
				tc++;
				pu(w, 0);
				while (!qu.empty()) {
					t = qu.top(); qu.pop();
					if (mn[t.c1] != t.c2) continue;
					mx = max(mx, t.c2);
					for (z = 0; z < a[t.c1].size(); z++) {
						pu(a[t.c1][z], t.c2 + b[t.c1][z]);
					}
				}
			}
			if (ans == -1 || mx < ans) ans = mx;
			a[i].pop_back(); a[j].pop_back();
			b[i].pop_back(); b[j].pop_back();
		}
	}
    return ans;
}

Compilation message

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:34:12: warning: division by zero [-Wdiv-by-zero]
   34 |   cout << 1/0;
      |           ~^~
shortcut.cpp:69:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |      for (z = 0; z < a[t.c1].size(); z++) {
      |                  ~~^~~~~~~~~~~~~~~~
shortcut.cpp:30:11: warning: unused variable 'k' [-Wunused-variable]
   30 |  ll i, j, k, w, z;
      |           ^

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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