oj.uz

Submission #232896

# Submission time Handle Problem Language Result Execution time Memory
232896 2020-05-18T15:46:37 Z anubhavdhar Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1081 ms 73848 KB 
#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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 7 ms 640 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 9 ms 896 KB Output is correct
13 Correct 8 ms 1152 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 512 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 7 ms 640 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 9 ms 896 KB Output is correct
13 Correct 8 ms 1152 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 512 KB Output is correct
16 Correct 728 ms 67088 KB Output is correct
17 Correct 106 ms 16120 KB Output is correct
18 Correct 172 ms 18168 KB Output is correct
19 Correct 1081 ms 73848 KB Output is correct
20 Correct 356 ms 56312 KB Output is correct
21 Correct 56 ms 7288 KB Output is correct
22 Correct 403 ms 53496 KB Output is correct