Submission #232896

#	Time	Username	Problem	Language	Result	Execution time	Memory
232896		anubhavdhar	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1081 ms	73848 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;}
// };

#define ind ss
#define wt ff.ss
#define to ff.ff
#define edge pair<pair<int, int>, int>
 
int travel_plan(int N,int M,int (* R)[2],int* L,int K,int* P)
{

	vector<edge> g[N+1];
	ll i, d[N+1], d2[N+1];
	FOR(i, N)
		d[i] = d2[i] = 1e9 + 2;
	d[N] = d2[N] = 0;
	FOR(i, M)
	{
		g[R[i][0]].pb(mp(mp(R[i][1], L[i]), i));
		g[R[i][1]].pb(mp(mp(R[i][0], L[i]), i));
	}
 
	set<ii> x; // (d,vertex);
	FOR(i, K)
	{
		x.insert(mp(0,P[i]));
		d[P[i]] = d2[P[i]] = 0;
	}
	set<ii> :: iterator it;
	while(!x.empty())
	{
		int a = (*(x.begin())).ss;
		x.erase(x.begin());
		for(edge pp : g[a])
		{
			if (d2[pp.to] >= d2[a] + pp.wt)
			{
				x.erase(mp(d2[pp.to],pp.to));
				ll aa = d2[a] + pp.wt, bb = d[pp.to];
				d[pp.to] = min(aa, bb);
				d2[pp.to] = max(aa, bb);
				// cout<<a<<" -> "<<pp.to<<", aa = "<<aa<<" and bb = "<<bb<<'\n';
				x.insert(mp(d2[pp.to],pp.to));
			}
			// else
				// cout<<"d2["<<pp.to<<"] = "<<d2[pp.to]<<" < d2["<<a<<"] + pp.wt = "<<d2[a]<<" + "<<pp.wt<<'\n';
		}
	} 

	// dbgLine;
 
	// FOR(i, N)
		// if(towards[i] < M)
			// open[towards[i]] = false;
 
	// FOR(i, N)
	// 	cout<<"d["<<i<<"] = "<<d[i]<<"\td2["<<i<<"] = "<<d2[i]<<'\n';
 
	// dbgLine;
/*
	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 ((towards[pp.to] != pp.ind or pp.ind >= M) && 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));
			}
		}
	}
*/
	// dbgLine;
	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;
}

12 17 2
0 2 1
0 4 1
2 3 1
2 5 1
3 6 1
4 5 1
5 6 1
7 8 1
8 9 1
10 11 1
11 12 1
4 7 1
5 8 1
6 9 1
7 10 1
8 11 1
9 12 1
6 12
*/

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