oj.uz

Submission #932382

# Submission time Handle Problem Language Result Execution time Memory
932382 2024-02-23T09:03:25 Z kxd Shortcut (IOI16_shortcut) C++17
0 / 100
 2000 ms 600 KB 
#define tj
#ifdef tj
#include "shortcut.h"
#endif
#include <bits/stdc++.h>
//#define DEBUG 1106
//#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define p_q priority_queue
#define m_p make_pair
#define pii pair<ll,ll>
#define endl '\n'
#define INIT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define forn(i,n) for (int i = 0; i < n; i++)
#define forn1(i,n) for (int i = 1; i <= n; i++)
#define all(x) x.begin(),x.end()
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#ifdef DEBUG
#define debug(x) cout << #x << ": " << x << endl;
#else
#define debug(x) 1106;
#endif
 
using namespace std;
const int N = 500;
const int inf = 1e9;
const ll INF = 1e18;
const int MOD = 1e9+7;
 
int n;
vector<pii> G[N];
ll dis[N];
 
long long src(int x, int dest) {
	p_q<pii, vector<pii>, greater<pii>> pq;
	memset(dis,-1,sizeof(dis));
	pq.push(m_p(0, x));
	dis[x] = 0;
	ll ans = 0;
	while (!pq.empty()) {
		pii c = pq.top();
		pq.pop();
		if (dis[c.sd] != c.ft) continue;
		//cout << c.sd << '|' << c.ft << endl;
		for (auto i : G[c.sd]) {
			if (dis[i.ft] == -1 || dis[i.ft] > i.sd+c.ft) {
				dis[i.ft] = i.sd+c.ft;
				chmax(ans,dis[i.ft]);
				pq.push(m_p(dis[i.ft], i.ft));
			}
		}
	}
	return dis[dest];
}
 
long long find_diameter() {
	ll ans = 0;
	forn(i,n*2+2) {
		forn(j,n*2+2)
			chmax(ans,src(i,j));
	}
	return ans;
}
 
long long find_shortcut(int n_, vector<int> l, vector<int> d, int c) {
    n = n_;
    forn(i,n) {
    	if(i!=n-1) {
    		G[i].pb({i+1,l[i]});
    		G[i+1].pb({i,l[i]});
		}
    	if(d[i]) {
    		G[i].pb({i+n,d[i]});
    		G[i+n].pb({i,d[i]});
		}
	}
	ll ans = INF;
	for(int i = 0; i < n-1; i++) {
		for(int j = i+1; j <= n-1; j++) {
			G[i].pb({j,c});
			G[j].pb({i,c});
			ll t = find_diameter();
			chmin(ans,t);
			G[i].pop_back();
			G[j].pop_back();
		}
	}
	return ans;
}
#ifndef tj
int main() {
    int n, c;
    assert(2 == scanf("%d%d", &n, &c));
    
    std::vector<int> l(n - 1);
    std::vector<int> d(n);
    for (int i = 0; i < n - 1; i++)
        assert(1 == scanf("%d", &l[i]));
    for (int i = 0; i < n; i++)
        assert(1 == scanf("%d", &d[i]));
    long long t = find_shortcut(n, l, d, c);
    printf("%lld\n", t);
    
    return 0;
}
#endif

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB n = 4, 80 is a correct answer
2 Correct 4 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 556 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 600 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 448 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 9 ms 344 KB n = 10, 1000000343 is a correct answer
18 Correct 9 ms 444 KB n = 10, 3189 is a correct answer
19 Correct 9 ms 444 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 348 KB n = 5, 12 is a correct answer
21 Correct 1 ms 348 KB n = 5, 25 is a correct answer
22 Correct 0 ms 348 KB n = 2, 122 is a correct answer
23 Correct 10 ms 348 KB n = 10, 117 is a correct answer
24 Correct 9 ms 344 KB n = 10, 336 is a correct answer
25 Correct 8 ms 348 KB n = 10, 438 is a correct answer
26 Correct 4 ms 348 KB n = 10, 206 is a correct answer
27 Correct 9 ms 448 KB n = 10, 636 is a correct answer
28 Correct 1 ms 348 KB n = 4, 2399 is a correct answer
29 Correct 10 ms 348 KB n = 10, 10992 is a correct answer
30 Correct 9 ms 448 KB n = 10, 3112 is a correct answer
31 Execution timed out 2052 ms 348 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB n = 4, 80 is a correct answer
2 Correct 4 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 556 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 600 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 448 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 9 ms 344 KB n = 10, 1000000343 is a correct answer
18 Correct 9 ms 444 KB n = 10, 3189 is a correct answer
19 Correct 9 ms 444 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 348 KB n = 5, 12 is a correct answer
21 Correct 1 ms 348 KB n = 5, 25 is a correct answer
22 Correct 0 ms 348 KB n = 2, 122 is a correct answer
23 Correct 10 ms 348 KB n = 10, 117 is a correct answer
24 Correct 9 ms 344 KB n = 10, 336 is a correct answer
25 Correct 8 ms 348 KB n = 10, 438 is a correct answer
26 Correct 4 ms 348 KB n = 10, 206 is a correct answer
27 Correct 9 ms 448 KB n = 10, 636 is a correct answer
28 Correct 1 ms 348 KB n = 4, 2399 is a correct answer
29 Correct 10 ms 348 KB n = 10, 10992 is a correct answer
30 Correct 9 ms 448 KB n = 10, 3112 is a correct answer
31 Execution timed out 2052 ms 348 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB n = 4, 80 is a correct answer
2 Correct 4 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 556 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 600 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 448 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 9 ms 344 KB n = 10, 1000000343 is a correct answer
18 Correct 9 ms 444 KB n = 10, 3189 is a correct answer
19 Correct 9 ms 444 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 348 KB n = 5, 12 is a correct answer
21 Correct 1 ms 348 KB n = 5, 25 is a correct answer
22 Correct 0 ms 348 KB n = 2, 122 is a correct answer
23 Correct 10 ms 348 KB n = 10, 117 is a correct answer
24 Correct 9 ms 344 KB n = 10, 336 is a correct answer
25 Correct 8 ms 348 KB n = 10, 438 is a correct answer
26 Correct 4 ms 348 KB n = 10, 206 is a correct answer
27 Correct 9 ms 448 KB n = 10, 636 is a correct answer
28 Correct 1 ms 348 KB n = 4, 2399 is a correct answer
29 Correct 10 ms 348 KB n = 10, 10992 is a correct answer
30 Correct 9 ms 448 KB n = 10, 3112 is a correct answer
31 Execution timed out 2052 ms 348 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB n = 4, 80 is a correct answer
2 Correct 4 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 556 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 600 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 448 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 9 ms 344 KB n = 10, 1000000343 is a correct answer
18 Correct 9 ms 444 KB n = 10, 3189 is a correct answer
19 Correct 9 ms 444 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 348 KB n = 5, 12 is a correct answer
21 Correct 1 ms 348 KB n = 5, 25 is a correct answer
22 Correct 0 ms 348 KB n = 2, 122 is a correct answer
23 Correct 10 ms 348 KB n = 10, 117 is a correct answer
24 Correct 9 ms 344 KB n = 10, 336 is a correct answer
25 Correct 8 ms 348 KB n = 10, 438 is a correct answer
26 Correct 4 ms 348 KB n = 10, 206 is a correct answer
27 Correct 9 ms 448 KB n = 10, 636 is a correct answer
28 Correct 1 ms 348 KB n = 4, 2399 is a correct answer
29 Correct 10 ms 348 KB n = 10, 10992 is a correct answer
30 Correct 9 ms 448 KB n = 10, 3112 is a correct answer
31 Execution timed out 2052 ms 348 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB n = 4, 80 is a correct answer
2 Correct 4 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 556 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 600 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 448 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 9 ms 344 KB n = 10, 1000000343 is a correct answer
18 Correct 9 ms 444 KB n = 10, 3189 is a correct answer
19 Correct 9 ms 444 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 348 KB n = 5, 12 is a correct answer
21 Correct 1 ms 348 KB n = 5, 25 is a correct answer
22 Correct 0 ms 348 KB n = 2, 122 is a correct answer
23 Correct 10 ms 348 KB n = 10, 117 is a correct answer
24 Correct 9 ms 344 KB n = 10, 336 is a correct answer
25 Correct 8 ms 348 KB n = 10, 438 is a correct answer
26 Correct 4 ms 348 KB n = 10, 206 is a correct answer
27 Correct 9 ms 448 KB n = 10, 636 is a correct answer
28 Correct 1 ms 348 KB n = 4, 2399 is a correct answer
29 Correct 10 ms 348 KB n = 10, 10992 is a correct answer
30 Correct 9 ms 448 KB n = 10, 3112 is a correct answer
31 Execution timed out 2052 ms 348 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB n = 4, 80 is a correct answer
2 Correct 4 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 556 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 600 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 448 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 9 ms 344 KB n = 10, 1000000343 is a correct answer
18 Correct 9 ms 444 KB n = 10, 3189 is a correct answer
19 Correct 9 ms 444 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 348 KB n = 5, 12 is a correct answer
21 Correct 1 ms 348 KB n = 5, 25 is a correct answer
22 Correct 0 ms 348 KB n = 2, 122 is a correct answer
23 Correct 10 ms 348 KB n = 10, 117 is a correct answer
24 Correct 9 ms 344 KB n = 10, 336 is a correct answer
25 Correct 8 ms 348 KB n = 10, 438 is a correct answer
26 Correct 4 ms 348 KB n = 10, 206 is a correct answer
27 Correct 9 ms 448 KB n = 10, 636 is a correct answer
28 Correct 1 ms 348 KB n = 4, 2399 is a correct answer
29 Correct 10 ms 348 KB n = 10, 10992 is a correct answer
30 Correct 9 ms 448 KB n = 10, 3112 is a correct answer
31 Execution timed out 2052 ms 348 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB n = 4, 80 is a correct answer
2 Correct 4 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 556 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 600 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 448 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 9 ms 344 KB n = 10, 1000000343 is a correct answer
18 Correct 9 ms 444 KB n = 10, 3189 is a correct answer
19 Correct 9 ms 444 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 348 KB n = 5, 12 is a correct answer
21 Correct 1 ms 348 KB n = 5, 25 is a correct answer
22 Correct 0 ms 348 KB n = 2, 122 is a correct answer
23 Correct 10 ms 348 KB n = 10, 117 is a correct answer
24 Correct 9 ms 344 KB n = 10, 336 is a correct answer
25 Correct 8 ms 348 KB n = 10, 438 is a correct answer
26 Correct 4 ms 348 KB n = 10, 206 is a correct answer
27 Correct 9 ms 448 KB n = 10, 636 is a correct answer
28 Correct 1 ms 348 KB n = 4, 2399 is a correct answer
29 Correct 10 ms 348 KB n = 10, 10992 is a correct answer
30 Correct 9 ms 448 KB n = 10, 3112 is a correct answer
31 Execution timed out 2052 ms 348 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB n = 4, 80 is a correct answer
2 Correct 4 ms 348 KB n = 9, 110 is a correct answer
3 Correct 1 ms 556 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 0 ms 600 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Correct 0 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 ms 348 KB n = 3, 3000000000 is a correct answer
13 Correct 0 ms 448 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 348 KB n = 4, 3000000001 is a correct answer
15 Correct 0 ms 348 KB n = 4, 4000000000 is a correct answer
16 Correct 1 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 9 ms 344 KB n = 10, 1000000343 is a correct answer
18 Correct 9 ms 444 KB n = 10, 3189 is a correct answer
19 Correct 9 ms 444 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 348 KB n = 5, 12 is a correct answer
21 Correct 1 ms 348 KB n = 5, 25 is a correct answer
22 Correct 0 ms 348 KB n = 2, 122 is a correct answer
23 Correct 10 ms 348 KB n = 10, 117 is a correct answer
24 Correct 9 ms 344 KB n = 10, 336 is a correct answer
25 Correct 8 ms 348 KB n = 10, 438 is a correct answer
26 Correct 4 ms 348 KB n = 10, 206 is a correct answer
27 Correct 9 ms 448 KB n = 10, 636 is a correct answer
28 Correct 1 ms 348 KB n = 4, 2399 is a correct answer
29 Correct 10 ms 348 KB n = 10, 10992 is a correct answer
30 Correct 9 ms 448 KB n = 10, 3112 is a correct answer
31 Execution timed out 2052 ms 348 KB Time limit exceeded
32 Halted 0 ms 0 KB -