oj.uz

Submission #889190

# Submission time Handle Problem Language Result Execution time Memory
889190 2023-12-19T07:04:34 Z Muhammad_Aneeq Shortcut (IOI16_shortcut) C++17
0 / 100
 9 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 9 ms 26204 KB n = 4, 80 is a correct answer
2 Correct 7 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 26204 KB n = 3, 4 is a correct answer
5 Correct 5 ms 26204 KB n = 2, 62 is a correct answer
6 Correct 6 ms 26400 KB n = 2, 3 is a correct answer
7 Correct 6 ms 26456 KB n = 3, 29 is a correct answer
8 Correct 6 ms 26204 KB n = 2, 3 is a correct answer
9 Correct 5 ms 26204 KB n = 2, 3 is a correct answer
10 Correct 6 ms 26204 KB n = 2, 2000000001 is a correct answer
11 Correct 6 ms 26316 KB n = 2, 3000000000 is a correct answer
12 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
13 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 7 ms 26200 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26204 KB n = 4, 80 is a correct answer
2 Correct 7 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 26204 KB n = 3, 4 is a correct answer
5 Correct 5 ms 26204 KB n = 2, 62 is a correct answer
6 Correct 6 ms 26400 KB n = 2, 3 is a correct answer
7 Correct 6 ms 26456 KB n = 3, 29 is a correct answer
8 Correct 6 ms 26204 KB n = 2, 3 is a correct answer
9 Correct 5 ms 26204 KB n = 2, 3 is a correct answer
10 Correct 6 ms 26204 KB n = 2, 2000000001 is a correct answer
11 Correct 6 ms 26316 KB n = 2, 3000000000 is a correct answer
12 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
13 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 7 ms 26200 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26204 KB n = 4, 80 is a correct answer
2 Correct 7 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 26204 KB n = 3, 4 is a correct answer
5 Correct 5 ms 26204 KB n = 2, 62 is a correct answer
6 Correct 6 ms 26400 KB n = 2, 3 is a correct answer
7 Correct 6 ms 26456 KB n = 3, 29 is a correct answer
8 Correct 6 ms 26204 KB n = 2, 3 is a correct answer
9 Correct 5 ms 26204 KB n = 2, 3 is a correct answer
10 Correct 6 ms 26204 KB n = 2, 2000000001 is a correct answer
11 Correct 6 ms 26316 KB n = 2, 3000000000 is a correct answer
12 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
13 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 7 ms 26200 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26204 KB n = 4, 80 is a correct answer
2 Correct 7 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 26204 KB n = 3, 4 is a correct answer
5 Correct 5 ms 26204 KB n = 2, 62 is a correct answer
6 Correct 6 ms 26400 KB n = 2, 3 is a correct answer
7 Correct 6 ms 26456 KB n = 3, 29 is a correct answer
8 Correct 6 ms 26204 KB n = 2, 3 is a correct answer
9 Correct 5 ms 26204 KB n = 2, 3 is a correct answer
10 Correct 6 ms 26204 KB n = 2, 2000000001 is a correct answer
11 Correct 6 ms 26316 KB n = 2, 3000000000 is a correct answer
12 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
13 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 7 ms 26200 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26204 KB n = 4, 80 is a correct answer
2 Correct 7 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 26204 KB n = 3, 4 is a correct answer
5 Correct 5 ms 26204 KB n = 2, 62 is a correct answer
6 Correct 6 ms 26400 KB n = 2, 3 is a correct answer
7 Correct 6 ms 26456 KB n = 3, 29 is a correct answer
8 Correct 6 ms 26204 KB n = 2, 3 is a correct answer
9 Correct 5 ms 26204 KB n = 2, 3 is a correct answer
10 Correct 6 ms 26204 KB n = 2, 2000000001 is a correct answer
11 Correct 6 ms 26316 KB n = 2, 3000000000 is a correct answer
12 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
13 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 7 ms 26200 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26204 KB n = 4, 80 is a correct answer
2 Correct 7 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 26204 KB n = 3, 4 is a correct answer
5 Correct 5 ms 26204 KB n = 2, 62 is a correct answer
6 Correct 6 ms 26400 KB n = 2, 3 is a correct answer
7 Correct 6 ms 26456 KB n = 3, 29 is a correct answer
8 Correct 6 ms 26204 KB n = 2, 3 is a correct answer
9 Correct 5 ms 26204 KB n = 2, 3 is a correct answer
10 Correct 6 ms 26204 KB n = 2, 2000000001 is a correct answer
11 Correct 6 ms 26316 KB n = 2, 3000000000 is a correct answer
12 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
13 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 7 ms 26200 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26204 KB n = 4, 80 is a correct answer
2 Correct 7 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 26204 KB n = 3, 4 is a correct answer
5 Correct 5 ms 26204 KB n = 2, 62 is a correct answer
6 Correct 6 ms 26400 KB n = 2, 3 is a correct answer
7 Correct 6 ms 26456 KB n = 3, 29 is a correct answer
8 Correct 6 ms 26204 KB n = 2, 3 is a correct answer
9 Correct 5 ms 26204 KB n = 2, 3 is a correct answer
10 Correct 6 ms 26204 KB n = 2, 2000000001 is a correct answer
11 Correct 6 ms 26316 KB n = 2, 3000000000 is a correct answer
12 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
13 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 7 ms 26200 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26204 KB n = 4, 80 is a correct answer
2 Correct 7 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 26204 KB n = 3, 4 is a correct answer
5 Correct 5 ms 26204 KB n = 2, 62 is a correct answer
6 Correct 6 ms 26400 KB n = 2, 3 is a correct answer
7 Correct 6 ms 26456 KB n = 3, 29 is a correct answer
8 Correct 6 ms 26204 KB n = 2, 3 is a correct answer
9 Correct 5 ms 26204 KB n = 2, 3 is a correct answer
10 Correct 6 ms 26204 KB n = 2, 2000000001 is a correct answer
11 Correct 6 ms 26316 KB n = 2, 3000000000 is a correct answer
12 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
13 Correct 6 ms 26204 KB n = 3, 3000000000 is a correct answer
14 Incorrect 7 ms 26200 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -