oj.uz

Submission #414694

# Submission time Handle Problem Language Result Execution time Memory
414694 2021-05-31T04:07:56 Z jeqcho Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 756 ms 62224 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define fi first
#define se second

int const n1=1e5+3;
bitset<n1> colored;
vpi adj[n1];
int to[n1];
pii cnt[n1];
int const INF=1e9;

// subtask 1,2,3

template<class T>
struct segmentTree
{
	// customise
	//init_v
	//comb
	//update
	
	int arr_sz;
	vector<T> seg;
	T init_v = {INF,INF};
	
	void init(int n, vector<T> &v)
	{
		int p2 = ceil(log2((long double) n));
		arr_sz = 1<<p2;
		seg.rsz(arr_sz*2-1);
		F0R(i,n)
		{
			seg[arr_sz-1 + i] = v[i];
		}
		FOR(i,n,arr_sz)
		{
			seg[arr_sz-1 + i] = init_v;
		}
		build(0,0,arr_sz);
	}
	
	T build(int x, int lx, int rx)
	{
		if(lx==rx-1)
		{
			return seg[x];
		}
		int md = (lx+rx)/2;
		T lef = build(2*x+1,lx,md);
		T rig = build(2*x+2,md,rx);
		seg[x] = comb(lef,rig);
		return seg[x];
	}
	
	T comb(T a, T b)
	{
		return min(a,b);
	}
	
	T query(int x, int lq, int rq, int lx, int rx)
	{
		if(rq<=lx || lq>=rx)
		{
			return init_v;
		}
		else if(lq<=lx && rq>=rx)
		{
			return seg[x];
		}
		else
		{
			int md=(lx+rx)/2;
			T lef = query(2*x+1,lq,rq,lx,md);
			T rig = query(2*x+2,lq,rq,md,rx);
			return comb(lef,rig);
		}
	}
	
	T query(int lq, int rq)
	{
		return query(0,lq,rq,0,arr_sz);
	}
	
	void update(int x, T v)
	{
		x += arr_sz-1;
		seg[x] = v;
		while(x>0)
		{
			x = (x-1)/2;
			seg[x] = comb(seg[2*x+1],seg[2*x+2]);
		}
	}
};

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	segmentTree<pii>seg;
	vpi a(N);
	F0R(i,N)
	{
		a[i]={INF,i};
	}
	seg.init(N,a);
	F0R(i,N)
	{
		cnt[i]={INF,INF};
	}
	vi nw;
	F0R(i,K)
	{
		colored[P[i]]=1;
		to[P[i]]=0;
		nw.pb(P[i]);
	}
	F0R(i,M)
	{
		int u=R[i][0];
		int v=R[i][1];
		adj[u].pb({v,L[i]});
		adj[v].pb({u,L[i]});
	}
	while(!colored[0])
	{
		trav(e,nw)
		{
			trav(chi,adj[e])
			{
				if(colored[chi.fi])continue;
				int cand = to[e]+chi.se;
				if(cand < cnt[chi.fi].fi)
				{
					cnt[chi.fi].se = cnt[chi.fi].fi;
					cnt[chi.fi].fi = cand;
				}
				else
				{
					cnt[chi.fi].se = min(cnt[chi.fi].se,cand);
				}
				seg.update(chi.fi,{cnt[chi.fi].se,chi.fi});
			}
		}
		nw.clear();
		pii nxt = seg.query(0,N);
		int rec = nxt.fi;
		nw.pb(nxt.se);
		trav(e,nw)
		{
			to[e]=rec;
			colored[e]=1;
			seg.update(e,{INF,INF});
		}
	}
	return (int)to[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2636 KB Output is correct
2 Correct 4 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 5 ms 2664 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 4 ms 2668 KB Output is correct
7 Correct 4 ms 2668 KB Output is correct
8 Correct 4 ms 2764 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2636 KB Output is correct
2 Correct 4 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 5 ms 2664 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 4 ms 2668 KB Output is correct
7 Correct 4 ms 2668 KB Output is correct
8 Correct 4 ms 2764 KB Output is correct
9 Correct 4 ms 2892 KB Output is correct
10 Correct 4 ms 2636 KB Output is correct
11 Correct 5 ms 2764 KB Output is correct
12 Correct 8 ms 3048 KB Output is correct
13 Correct 6 ms 3148 KB Output is correct
14 Correct 4 ms 2636 KB Output is correct
15 Correct 4 ms 2764 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2636 KB Output is correct
2 Correct 4 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 5 ms 2664 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 4 ms 2668 KB Output is correct
7 Correct 4 ms 2668 KB Output is correct
8 Correct 4 ms 2764 KB Output is correct
9 Correct 4 ms 2892 KB Output is correct
10 Correct 4 ms 2636 KB Output is correct
11 Correct 5 ms 2764 KB Output is correct
12 Correct 8 ms 3048 KB Output is correct
13 Correct 6 ms 3148 KB Output is correct
14 Correct 4 ms 2636 KB Output is correct
15 Correct 4 ms 2764 KB Output is correct
16 Correct 715 ms 57612 KB Output is correct
17 Correct 147 ms 16964 KB Output is correct
18 Correct 134 ms 18460 KB Output is correct
19 Correct 756 ms 62224 KB Output is correct
20 Correct 330 ms 49544 KB Output is correct
21 Correct 65 ms 8452 KB Output is correct
22 Correct 486 ms 46872 KB Output is correct