Submission #232865

#	Time	Username	Problem	Language	Result	Execution time	Memory
232865		anubhavdhar	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	4 ms	384 KiB

crocodile

#include<bits/stdc++.h>
// #include "crocodile.h"
 
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first 
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define dbgLine cout<<"Line : "<<__LINE__<<'\n'
#define all(x) (x).begin(),(x).end()
 
using namespace std;
/*
const short int __PRECISION = 10;
 
const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 2e5+5;
const ll ROOTN = 320;
 
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
*/
struct edge
{
	ll to, wt, ind;
	inline void reset(){to = -1; wt = -1; ind = -1;}
	inline void set(ll t, ll w, ll in){to = t; wt = w; ind = in;}
};
 
int travel_plan(int N,int M,int (* R)[2],int* L,int K,int* P)
{
	vector<edge> g[N+1];
	ll towards[N+1], i, d[N+1], d2[N+1];
	bool open[M+K+1];
	edge Neutral;
	Neutral.reset();
	FOR(i, N)
		d[i] = d2[i] = 1e9 + 2;
	d[N] = d2[N] = 0;
	FOR(i, M)
	{
		g[R[i][0]].pb(Neutral);
		g[R[i][1]].pb(Neutral);
		g[R[i][0]][g[R[i][0]].size() - 1].set(R[i][1], L[i], i);
		g[R[i][1]][g[R[i][1]].size() - 1].set(R[i][0], L[i], i);
		open[i] = true;
	}
	FOR(i, K)
	{
		g[P[i]].pb(Neutral);
		g[N].pb(Neutral);
		g[P[i]][g[P[i]].size() - 1].set(N, 0, i + M);
		g[N][g[N].size() - 1].set(P[i], 0, i + M);
		open[i + M] = true;
	}
 
	set<ii> x; // (d,vertex);
	x.insert(mp(0,N));
	set<ii> :: iterator it;
	while(!x.empty())
	{
		int a = (*(x.begin())).ss;
		x.erase(x.begin());
		for(edge pp : g[a])
		{
			if (d[pp.to] > d[a] + pp.wt)
			{
				x.erase(mp(d[pp.to],pp.to));
				d[pp.to] = d[a] + pp.wt;
				x.insert(mp(d[pp.to],pp.to));
				towards[pp.to] = pp.ind;
			}
		}
	} 
 
	FOR(i, N)
		if(towards[i] < M)
			open[towards[i]] = false;
 
	// FOR(i, N)
	// 	cout<<i<<" -> "<<((towards[i] < M) ? (R[towards[i]][0] + R[towards[i]][1] - i) : -1 )<<"\t d["<<i<<"] = "<<d[i]<<'\n';
 
	x.clear();
	x.insert(mp(0,N));
	while(!x.empty())
	{
		// cout<<"x contains : "; for(ii vv : x) cout<<vv.ff<<' '<<vv.ss<<'\t'; cout<<endl;
		int a = (*(x.begin())).ss;
		x.erase(x.begin());
		for(edge pp : g[a])
		{
			if (open[pp.ind] && d2[pp.to] > d2[a] + pp.wt)
			{
				// cout<<"updating "<<pp.to<<" from "<<a<<endl;
				x.erase(mp(d2[pp.to],pp.to));
				d2[pp.to] = d2[a] + pp.wt;
				x.insert(mp(d2[pp.to],pp.to));
			}
		}
	}
 
	return d2[0];
}
/*
int main()
{
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N, M, K, i;
	cin>>N>>M>>K;
	int R[M][2], L[M], P[K];
	FOR(i, M)	cin>>R[i][0]>>R[i][1]>>L[i];
	FOR(i, K)	cin>>P[i];
	cout<<travel_plan(N,M,R,L,K,P);
	return 0;
}

5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
*/

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