oj.uz

Submission #889191

# Submission time Handle Problem Language Result Execution time Memory
889191 2023-12-19T07:05:21 Z Muhammad_Aneeq Shortcut (IOI16_shortcut) C++17
0 / 100
 2000 ms 26456 KB 
#include <vector>
#include <set>
using namespace std;
int const N=1e6+10;
vector<pair<int,int>>nei[N]={};
long long dis[N]={};
int vis[N]={};
long long ans=1e17+10;
int ns;
long long bfs(int x)
{
	for (int i=0;i<ns;i++)
	{
		vis[i]=0;
		dis[i]=1e17+10;
	}
	dis[x]=0;
	set<pair<int,int>>s;
	s.insert({0,x});
	while (s.size())
	{
		int x=(*begin(s)).second;
		s.erase(*begin(s));
		// if (vis[x])
		// 	continue;
		// vis[x]=1;
		for (auto i:nei[x])
		{
			if (dis[i.first]>dis[x]+i.second)
			{
				s.erase({dis[i.first],i.first});
				dis[i.first]=dis[x]+i.second;
				s.insert({dis[i.first],i.first});
			}
		}
	}
	long long z=0;
	for (int i=0;i<ns;i++)
		z=max(z,dis[i]);
	return z;
}
void find()
{
	long long f=0;
	for (int i=0;i<ns;i++)
	{
		long long z=bfs(i);
		f=max(f,z);
	}
	ans=min(ans,f);
}
long long find_shortcut(int n,vector<int>l,vector<int>d,int c)
{
	for (int i=0;i<n-1;i++)
	{
		nei[i].push_back({i+1,l[i]});
		nei[i+1].push_back({i,l[i]});
	}
	ns=n;
	for (int i=0;i<n;i++)
	{
		if (d[i])
		{
			nei[i].push_back({ns,d[i]});
			nei[ns].push_back({i,d[i]});
			ns++;
		}
	}
	for (int i=0;i<n;i++)
		for (int j=i+1;j<n;j++)
		{
			nei[i].push_back({j,c});
			nei[j].push_back({i,c});
			find();
			nei[i].pop_back();
			nei[j].pop_back()		;
		}
	return ans;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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