oj.uz

Submission #986315

# Submission time Handle Problem Language Result Execution time Memory
986315 2024-05-20T09:57:43 Z Pyqe Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 358 ms 93776 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long nr[100069][2];
vector<pair<long long,long long>> al[100069];
priority_queue<pair<long long,long long>> pq;
bitset<100069> vtd;

int travel_plan(int n,int m,int aa[][2],int wa[],int d,int ex[])
{
	long long i,j,ii,k,l,w,sz,ww;
	
	for(i=0;i<m;i++)
	{
		al[aa[i][0]].push_back({aa[i][1],wa[i]});
		al[aa[i][1]].push_back({aa[i][0],wa[i]});
	}
	for(i=0;i<n;i++)
	{
		for(ii=0;ii<2;ii++)
		{
			nr[i][ii]=1e18;
		}
	}
	for(i=0;i<d;i++)
	{
		pq.push({0,ex[i]});
		nr[ex[i]][0]=0;
		nr[ex[i]][1]=0;
	}
	for(;!pq.empty();)
	{
		k=pq.top().sc;
		w=-pq.top().fr;
		pq.pop();
		if(!k)
		{
			break;
		}
		if(vtd[k])
		{
			continue;
		}
		vtd[k]=1;
		sz=al[k].size();
		for(i=0;i<sz;i++)
		{
			l=al[k][i].fr;
			ww=al[k][i].sc;
			for(ii=0;ii<2;ii++)
			{
				if(w+ww<=nr[l][ii])
				{
					for(j=1;j>ii;j--)
					{
						nr[l][j]=nr[l][j-1];
					}
					nr[l][ii]=w+ww;
					if(nr[l][1]<1000000000000000000)
					{
						pq.push({-nr[l][1],l});
					}
					break;
				}
			}
		}
	}
	return w;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:74:9: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |  return w;
      |         ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8824 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8824 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 4 ms 9308 KB Output is correct
13 Correct 4 ms 9308 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8824 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 4 ms 9308 KB Output is correct
13 Correct 4 ms 9308 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 304 ms 86864 KB Output is correct
17 Correct 53 ms 21840 KB Output is correct
18 Correct 63 ms 24148 KB Output is correct
19 Correct 358 ms 93776 KB Output is correct
20 Correct 227 ms 72540 KB Output is correct
21 Correct 28 ms 16212 KB Output is correct
22 Correct 236 ms 69320 KB Output is correct