Submission #1175177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175177		Dedibeat	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	2 ms	1608 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define F first
#define S second
#define MAX_N 50000
#define MAX_M 10000000
vector<pair<int, int>> adj[MAX_N];
pair<ll, ll> t[4 * MAX_N + 5];
int ans[4 * MAX_N + 5];
void print(int v, int tl, int tr)
{
	if(tl == tr) cout << "(" << t[v].F << "," << t[v].S << ") ";
	else {
		int tm = (tl + tr) / 2;
		print(2 * v, tl, tm);
		print(2 * v  + 1, tm + 1, tr);
	}
}
void print_t(int N)
{
	print(1, 0, N);
	cout << "\n\n";
}
void add(int v, ll val)
{
//	cout << "add " << v << " " << val << endl;
	if(val <= t[v].S) t[v].F = t[v].S, t[v].S = val;
	else if(val <= t[v].F) t[v].F = val;
}
void upd(int v, int tl, int tr, int pos, ll val)
{
	if(tl == tr) add(v, val), ans[v] = tl;
	else 
	{
		int tm = (tl + tr) / 2;
		if(pos <= tm) upd(2 * v, tl, tm, pos, val);
		else upd(2 * v + 1, tm + 1, tr, pos, val);
		if(t[2 * v] < t[2 * v + 1])
			ans[v] = ans[2 * v], t[v] = t[2 * v];
		else ans[v] = ans[2 * v + 1], t[v] = t[2 * v + 1];
	}
}

void mark(int v, int tl, int tr, int pos)
{
	if(tl == tr) t[v] = {1e18, 1e18}, ans[v] = tl;
	else 
	{
		int tm = (tl + tr) / 2;
		if(pos <= tm) mark(2 * v, tl, tm, pos);
		else mark(2 * v + 1, tm + 1, tr, pos);
		if(t[2 * v] < t[2 * v + 1])
			ans[v] = ans[2 * v], t[v] = t[2 * v];
		else ans[v] = ans[2 * v + 1], t[v] = t[2 * v + 1];
	}
}


int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  	for(int i = 0; i < N; i++)
	{
		int u = R[i][0], v = R[i][1], w = L[i];
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}	
	
	for(int i = 0; i < 4 * N + 5; i++)
		t[i] = {1e18, 1e18};
	
	for(int i = 0; i < K; i++)
	{
		int v = P[i];
		if(v == 0) return 0;
		for(auto [u, w] : adj[v])
		{
		//	cout << "upd" << u << " " << w << endl;
			upd(1, 0, N, u, w);
		}
	}
//	print_t(N);
	for(int i = 0; i < N; i++)
	{
		int v = ans[1];
		auto [f, s] = t[1];
		if(v == 0)
		{
			return f;
		}
		for(auto [u, w] : adj[v])
		{
			upd(1, 0, N, u, f + w);
		}
		mark(1, 0, N, v);
	//	print_t(N);
	}
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:99:1: warning: control reaches end of non-void function [-Wreturn-type]
   99 | }
      | ^

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11