oj.uz

Submission #411829

# Submission time Handle Problem Language Result Execution time Memory
411829 2021-05-26T04:58:00 Z jeqcho Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 724 ms 62620 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];
pair<int,pii>cnt[n1];
int const INF=1e9;

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].fi=0;
		cnt[i].se={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;
				++cnt[chi.fi].fi;
				int cand = to[e]+chi.se;
				if(cand < cnt[chi.fi].se.fi)
				{
					cnt[chi.fi].se.se = cnt[chi.fi].se.fi;
					cnt[chi.fi].se.fi = cand;
				}
				else
				{
					cnt[chi.fi].se.se = min(cnt[chi.fi].se.se,cand);
				}
				seg.update(chi.fi,{cnt[chi.fi].se.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 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 4 ms 2764 KB Output is correct
8 Correct 4 ms 2680 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 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 4 ms 2764 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 5 ms 2764 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 3 ms 2664 KB Output is correct
12 Correct 10 ms 3048 KB Output is correct
13 Correct 5 ms 3028 KB Output is correct
14 Correct 4 ms 2636 KB Output is correct
15 Correct 4 ms 2636 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 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 4 ms 2764 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 5 ms 2764 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 3 ms 2664 KB Output is correct
12 Correct 10 ms 3048 KB Output is correct
13 Correct 5 ms 3028 KB Output is correct
14 Correct 4 ms 2636 KB Output is correct
15 Correct 4 ms 2636 KB Output is correct
16 Correct 685 ms 41692 KB Output is correct
17 Correct 144 ms 14016 KB Output is correct
18 Correct 138 ms 18864 KB Output is correct
19 Correct 724 ms 62620 KB Output is correct
20 Correct 313 ms 49620 KB Output is correct
21 Correct 71 ms 8600 KB Output is correct
22 Correct 502 ms 46916 KB Output is correct