oj.uz

Submission #867592

# Submission time Handle Problem Language Result Execution time Memory
867592 2023-10-28T20:14:27 Z thegamercoder19 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 410 ms 77612 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

#define M_PI       3.14159265358979323846
#define FILER 0
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const ll MOD = pow(10, 9) + 7;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const ull INFUL = 0x3f3f3f3f3f3f3f3f;
const ll INFT = 0x3f3f3f3f;
const ull MAX = 1LL << 24;
const ll MODD = 998244353;
const double EPS = 1e-10;
#define V vector
#define pll pair<ll, ll>
#define pull2 pair<ull,ull>
#define MS multiset
//#define M map
#define Q queue
#define PQ priority_queue
#define IOF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define FOR(typ,i,a,b,c) for(typ i = a; i < b; i += c)
#define FORR(typ,i,a,b,c) for(typ i = a; i > b; i -= c)
#define FORA(a,i) for(auto &i : a)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define sorta(a) sort(all(a))
#define sortd(a) sort(all(a), greater<ll>())
#define setp(x) setprecision(x)<<fixed
#define RET return
#define log(a,b) log(b)/log(a)
#define WH(s) while(s)
#define WHI(t) WH(t--)
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
#define YESNO(s) cout << (s ? "YES" : "NO") << endl;
#define YesNo(s) cout<<(s?"Yes":"No")<<endl;
#define TYP 0
using namespace std;
#include "crocodile.h"
V<V<pll>> g, g1;
V<bool> dp;
V<pll> d;
void dfs(ll u, ll p)
{
	ll m = INFL, mu = -1;
	FORA(g1[u], v)
		if (v.first != p)
		{
			dfs(v.first, u);
			if (m > dp[v.first] + v.second)
				mu = v.first, m = dp[v.first] + v.second;
		}
	if (g1[u].size() != 1 || (g1[u].size()==1 && g1[u][0].first != p))
	{
		m = INFL;
		FORA(g1[u], v)
			if (v.first != p && v.first != mu)
				m = min(m, dp[v.first] + v.second);
		dp[u] = m;
	}

}

void dijk(int& k, int* p)
{
	PQ<pll, V<pll>, greater<pll>> pq;
	FOR(ll, i, 0, k, 1)pq.push({ 0,p[i] }), d[p[i]] = { 0,0 };// , dp[p[i]] = 1;
	WH(!pq.empty())
	{
		ll du = pq.top().first, u = pq.top().second;
		pq.pop();
		if (du != d[u].second || dp[u])continue;
		dp[u] = 1;
		FORA(g[u], v)
		{

			if (d[v.first].first > du + v.second)
			{
				d[v.first] = { du + v.second, d[v.first].first };
				pq.push({ d[v.first].second , v.first });
			}
			else if (d[v.first].second > du + v.second)
			{
				d[v.first] = { d[v.first].first , du + v.second};
				pq.push({ d[v.first].second , v.first });
			}
		}
	}

}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	g.resize(N + 1);  d.resize(N + 1, {INFL,INFL}); dp.resize(N + 1);
	FOR(ll, i, 0, M, 1)g[R[i][0]].push_back({ R[i][1], L[i] }), g[R[i][1]].push_back({ R[i][0], L[i] });
	dijk(K, P);
	RET d[0].second;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4668 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 3 ms 4956 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4668 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 3 ms 4956 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 320 ms 69896 KB Output is correct
17 Correct 67 ms 18376 KB Output is correct
18 Correct 86 ms 20532 KB Output is correct
19 Correct 410 ms 77612 KB Output is correct
20 Correct 202 ms 52816 KB Output is correct
21 Correct 30 ms 10444 KB Output is correct
22 Correct 228 ms 51008 KB Output is correct