oj.uz

Submission #419485

# Submission time Handle Problem Language Result Execution time Memory
419485 2021-06-07T07:42:44 Z KalasLavas Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 663 ms 68176 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//#undef LOCALKL
#define IO \
ios_base::sync_with_stdio(0);(cin).tie(0);(cout).tie(0)
#define y1 y1_
#define prev prev_
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#ifdef LOCALKL
// #define cerr cerr<<"\33[1;32m"
// #define cout cout<<"\33[0m"
#else
#ifndef OO
#define endl '\n'
#define cerr if(1){}else cerr
#endif
#endif
#define OK cout<<"OK\n"<<endl;
#define setpre(k) fixed<<setprecision(k)
#define mmset(k,y) memset(k,y,sizeof(k))
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using pll = pair<long long,long long>;
using ull = unsigned long long;
using intt = long long;
using ll = long long;
using ld = long double;

const ll m9 = 998244353;
const ll m7 = 1000000007;
const ll m18 = 1000000000000000000;
const ll i127 = 2193062143;
const ll l127 = 9187201950435737471;

vector<pii>g[100001];

ll d1[100001], d2[100001];
bool c[100001];
priority_queue<pll>q;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	memset(d1, 127, sizeof(d1));
	memset(d2, 127, sizeof(d2));
	for(int i=0;i<M;i++)
	{
		g[R[i][0]].emplace_back(R[i][1], L[i]);
		g[R[i][1]].emplace_back(R[i][0], L[i]);
	}
	for(int i=0;i<K;i++)
	{
		q.emplace(0, P[i]);
		d1[P[i]]=d2[P[i]]=0;
	}
	while(!q.empty())
	{
		ll v, d;
		v = q.top().S;
		d =-q.top().F;
		q.pop();
		if(c[v]) continue;
		c[v]=1;
		for(auto u : g[v])
			if(!c[u.F] and d2[u.F] > d+u.S)
			{
				d2[u.F] = d+u.S;
				if(d1[u.F]>d2[u.F]) swap(d1[u.F], d2[u.F]);
				q.emplace(-d2[u.F], u.F);
			}
	}
	return d2[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
3 Correct 3 ms 4172 KB Output is correct
4 Correct 3 ms 4300 KB Output is correct
5 Correct 3 ms 4300 KB Output is correct
6 Correct 3 ms 4172 KB Output is correct
7 Correct 4 ms 4300 KB Output is correct
8 Correct 3 ms 4300 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
3 Correct 3 ms 4172 KB Output is correct
4 Correct 3 ms 4300 KB Output is correct
5 Correct 3 ms 4300 KB Output is correct
6 Correct 3 ms 4172 KB Output is correct
7 Correct 4 ms 4300 KB Output is correct
8 Correct 3 ms 4300 KB Output is correct
9 Correct 5 ms 4428 KB Output is correct
10 Correct 3 ms 4172 KB Output is correct
11 Correct 4 ms 4300 KB Output is correct
12 Correct 7 ms 4768 KB Output is correct
13 Correct 6 ms 4732 KB Output is correct
14 Correct 3 ms 4204 KB Output is correct
15 Correct 4 ms 4300 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
3 Correct 3 ms 4172 KB Output is correct
4 Correct 3 ms 4300 KB Output is correct
5 Correct 3 ms 4300 KB Output is correct
6 Correct 3 ms 4172 KB Output is correct
7 Correct 4 ms 4300 KB Output is correct
8 Correct 3 ms 4300 KB Output is correct
9 Correct 5 ms 4428 KB Output is correct
10 Correct 3 ms 4172 KB Output is correct
11 Correct 4 ms 4300 KB Output is correct
12 Correct 7 ms 4768 KB Output is correct
13 Correct 6 ms 4732 KB Output is correct
14 Correct 3 ms 4204 KB Output is correct
15 Correct 4 ms 4300 KB Output is correct
16 Correct 523 ms 61704 KB Output is correct
17 Correct 108 ms 16744 KB Output is correct
18 Correct 134 ms 18272 KB Output is correct
19 Correct 663 ms 68176 KB Output is correct
20 Correct 326 ms 51116 KB Output is correct
21 Correct 51 ms 9616 KB Output is correct
22 Correct 358 ms 47968 KB Output is correct