oj.uz

Submission #889186

# Submission time Handle Problem Language Result Execution time Memory
889186 2023-12-19T06:54:06 Z Muhammad_Aneeq Shortcut (IOI16_shortcut) C++17
0 / 100
 2000 ms 48216 KB 
#include <vector>
#include <set>
using namespace std;
int const N=1e6+10;
multiset<pair<int,int>>nei[N]={};
long long dis[N]={};
long long ans=1e17+10;
int ns;
long long bfs(int x)
{
	for (int i=0;i<ns;i++)
		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));
		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].insert({i+1,l[i]});
		nei[i+1].insert({i,l[i]});
	}
	ns=n;
	for (int i=0;i<n;i++)
	{
		if (d[i])
		{
			nei[i].insert({ns,d[i]});
			nei[ns].insert({i,d[i]});
			ns++;
		}
	}
	for (int i=0;i<n;i++)
		for (int j=i+1;j<n;j++)
		{
			nei[i].insert({j,c});
			nei[j].insert({i,c});
			find();
			nei[i].erase(nei[i].find({j,c}));
			nei[j].erase(nei[j].find({i,c}));
		}
	return ans;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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