oj.uz

Submission #867591

# Submission time Handle Problem Language Result Execution time Memory
867591 2023-10-28T20:12:45 Z thegamercoder19 Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 401 ms 96008 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<ll> 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 };
	WH(!pq.empty())
	{
		ll du = pq.top().first, u = pq.top().second;
		pq.pop();
		if (du != d[u].second)continue;
		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, INFL);
	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 4444 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4544 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 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 4444 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4544 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4880 KB Output is correct
12 Correct 3 ms 4952 KB Output is correct
13 Correct 4 ms 5208 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4564 KB Output is correct

Subtask #3
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 4444 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4544 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4880 KB Output is correct
12 Correct 3 ms 4952 KB Output is correct
13 Correct 4 ms 5208 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4564 KB Output is correct
16 Correct 316 ms 84512 KB Output is correct
17 Correct 76 ms 22432 KB Output is correct
18 Correct 105 ms 24772 KB Output is correct
19 Correct 401 ms 96008 KB Output is correct
20 Correct 229 ms 66204 KB Output is correct
21 Correct 34 ms 11992 KB Output is correct
22 Incorrect 236 ms 64920 KB Output isn't correct
23 Halted 0 ms 0 KB -