oj.uz

Submission #988787

# Submission time Handle Problem Language Result Execution time Memory
988787 2024-05-26T07:42:55 Z vjudge1 Cyberland (APIO23_cyberland) C++17
97 / 100
 665 ms 1115116 KB 
#include <algorithm>
#include <queue>
const int Nx=100010;
const double inf=1e24;
int n,m,k,h,ab[Nx];
struct edge{int to,nex,val,typ;};
edge a[300*Nx];
int head[75*Nx],cnt;
void add(int u,int v,int w,int t)
{
	a[++cnt]=edge{v,head[u],w,t};
	head[u]=cnt;
}
struct node
{
	int idx;double val;
	bool operator < (const node &x) const
	{
		if(idx/n!=x.idx/n)
			return idx/n>x.idx/n;
		return val>x.val;
	}
};
int id(int x,int lev){return x+lev*n;}
void find_zpair(int p)
{
	ab[p]=1;
	int i;
	for(i=head[p];i;i=a[i].nex)
	{
		if(ab[a[i].to]==0&&p!=h)
			find_zpair(a[i].to);
	}
}
double dis[75*Nx];
int fin[75*Nx];
void clear_all()
{
	int i;
	for(i=0;i<n;i++)
		ab[i]=0;
	for(i=0;i<=(k+1)*n+1;i++)
		head[i]=dis[i]=fin[i]=0;
	cnt=n=m=k=h=0;
}
double solve(int N,int M,int K,int H,std::vector<int> X,std::vector<int> Y,std::vector<int> C,std::vector<int> arr)
{
	clear_all();
	n=N,m=M,k=K,h=H;
	int i,j,now,fx,fy;
	for(i=0;i<M;i++)
	{
		add(X[i],Y[i],C[i],1);
		add(Y[i],X[i],C[i],1);
	}
	find_zpair(0);
	if(ab[H]==0)
		return -1;
	for(i=0;i<=N;i++)
		head[i]=0;
	cnt=0;
	for(i=0;i<M;i++)
	{
		for(j=0;j<=K;j++)
		{
			if(X[i]!=H)
				add(id(X[i],j),id(Y[i],j),C[i],1);
			if(Y[i]!=H)
				add(id(Y[i],j),id(X[i],j),C[i],1);
			if(j!=K&&X[i]!=H&&arr[Y[i]]==2)
				add(id(X[i],j),id(Y[i],j+1),C[i],2);
			if(j!=K&&Y[i]!=H&&arr[X[i]]==2)
				add(id(Y[i],j),id(X[i],j+1),C[i],2);
		}
	}
	for(i=0;i<=(K+1)*N+1;i++)
		dis[i]=inf,fin[i]=0;
	std::priority_queue<node> hea;
	for(i=0;i<N;i++)
	{
		if(arr[i]==0&&ab[i]==1)
		{
			hea.push(node{i,0});
			dis[i]=0;
		}
	}
	hea.push(node{0,0});
	dis[0]=0;
	while(hea.size())
	{
		node ax=hea.top();
		hea.pop();
		now=ax.idx;
		if(fin[now])
			continue;
		fin[now]=1;
		for(i=head[now];i;i=a[i].nex)
		{
			if(dis[a[i].to]>(dis[now]+a[i].val)/a[i].typ)
			{
				dis[a[i].to]=(dis[now]+a[i].val)/a[i].typ;
				if(!fin[a[i].to])
					hea.push(node{a[i].to,dis[a[i].to]});
			}
		}
	}
	double ans=inf;
	for(i=0;i<=K;i++)
		ans=std::min(ans,dis[id(H,i)]);
	return ans;
}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:50:14: warning: unused variable 'fx' [-Wunused-variable]
   50 |  int i,j,now,fx,fy;
      |              ^~
cyberland.cpp:50:17: warning: unused variable 'fy' [-Wunused-variable]
   50 |  int i,j,now,fx,fy;
      |                 ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7004 KB Correct.
2 Correct 14 ms 7000 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7516 KB Correct.
2 Correct 26 ms 7772 KB Correct.
3 Correct 25 ms 7772 KB Correct.
4 Correct 27 ms 7772 KB Correct.
5 Correct 26 ms 7764 KB Correct.
6 Correct 25 ms 21124 KB Correct.
7 Correct 31 ms 21116 KB Correct.
8 Correct 16 ms 36700 KB Correct.
9 Correct 28 ms 7548 KB Correct.
10 Correct 24 ms 7512 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7760 KB Correct.
2 Correct 26 ms 7760 KB Correct.
3 Correct 24 ms 6928 KB Correct.
4 Correct 26 ms 7568 KB Correct.
5 Correct 25 ms 7512 KB Correct.
6 Correct 8 ms 18264 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 110932 KB Correct.
2 Correct 123 ms 7760 KB Correct.
3 Correct 110 ms 7724 KB Correct.
4 Correct 118 ms 7764 KB Correct.
5 Correct 77 ms 7540 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 7512 KB Correct.
2 Correct 30 ms 7772 KB Correct.
3 Correct 25 ms 7800 KB Correct.
4 Correct 30 ms 21584 KB Correct.
5 Correct 19 ms 7256 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 7772 KB Correct.
2 Correct 19 ms 7516 KB Correct.
3 Correct 19 ms 12928 KB Correct.
4 Correct 16 ms 22140 KB Correct.
5 Correct 20 ms 7516 KB Correct.
6 Correct 21 ms 7812 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 7644 KB Correct.
2 Correct 21 ms 11096 KB Correct.
3 Correct 359 ms 93520 KB Correct.
4 Correct 227 ms 31824 KB Correct.
5 Correct 556 ms 127432 KB Correct.
6 Correct 306 ms 107216 KB Correct.
7 Correct 225 ms 29292 KB Correct.
8 Correct 203 ms 12884 KB Correct.
9 Correct 105 ms 7708 KB Correct.
10 Correct 90 ms 7760 KB Correct.
11 Correct 211 ms 8764 KB Correct.
12 Correct 113 ms 7664 KB Correct.
13 Correct 114 ms 7664 KB Correct.
14 Correct 194 ms 27808 KB Correct.
15 Correct 207 ms 15716 KB Correct.
16 Correct 104 ms 7796 KB Correct.
17 Correct 128 ms 7760 KB Correct.
18 Correct 111 ms 7704 KB Correct.
19 Correct 300 ms 8788 KB Correct.
20 Correct 7 ms 6488 KB Correct.
21 Correct 8 ms 6748 KB Correct.
22 Correct 22 ms 17244 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 665 ms 1115116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -