oj.uz

Submission #804548

# Submission time Handle Problem Language Result Execution time Memory
804548 2023-08-03T09:43:54 Z LIF Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 489 ms 63376 KB 
#include <bits/stdc++.h>
#include <queue>
using namespace std;
int cnt = 0;
struct edg
{
	int to;
	int next;
	long long int val;
}edge[300005];
struct node
{
	long long int val1;
	long long int val2;
	int id;
};
node dis[300005];
int head[300005];
void add(int x,int y,int val)
{
	cnt++;
	edge[cnt].to = y;
	edge[cnt].next = head[x];
	edge[cnt].val = val;
	head[x] = cnt; 
}
priority_queue<node> q;
bool operator < (node x,node y)
{
	return x.val2 > y.val2;
}
bool vis[300005];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	//cout<<"yeah"<<endl;
	for(int i=0;i<M;i++)add(R[i][0],R[i][1],L[i]);
	for(int i=0;i<M;i++)add(R[i][1],R[i][0],L[i]);
	for(int i=0;i<N;i++)
	{
		dis[i].val1 = 1e18;
		dis[i].val2 = 1e18;
		dis[i].id = i;
	}
	for(int i=0;i<K;i++)
	{
		dis[P[i]].val1 = 0;
		dis[P[i]].val2 = 0;
	}
	for(int i=0;i<K;i++)
	{
		q.push(dis[P[i]]);
	} 
	while(q.empty() == false)
	{
		node now = q.top();
		int val = now.val2;
		q.pop();
		
		if(vis[now.id] == true)continue;
		vis[now.id] = true;
		for(int i=head[now.id];i!=0;i=edge[i].next)
		{
			int to = edge[i].to;
			if(dis[to].val1 > dis[now.id].val2 + edge[i].val)
			{
				dis[to].val2 = dis[to].val1;
				dis[to].val1 = dis[now.id].val2 + edge[i].val;
				if(vis[to] == false)q.push(dis[to]);
			}
			else
			{
				if(dis[to].val2 > dis[now.id].val2 + edge[i].val)
				{
					dis[to].val2 = dis[now.id].val2 + edge[i].val;
					if(vis[to] == false)q.push(dis[to]);
				}
			}
		}
	}
  return dis[0].val2;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:56:7: warning: unused variable 'val' [-Wunused-variable]
   56 |   int val = now.val2;
      |       ^~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 452 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 452 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 584 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 3 ms 852 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 452 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 584 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 3 ms 852 KB Output is correct
13 Correct 2 ms 852 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Incorrect 489 ms 63376 KB Output isn't correct
17 Halted 0 ms 0 KB -