Submission #340493

#	Time	Username	Problem	Language	Result	Execution time	Memory
340493		Kerim	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	593 ms	61544 KiB

crocodile

#include "crocodile.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int vis[MAXN],dis[MAXN][2];
vector<PII>adj[MAXN];
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]){
	for(int i=0;i<m;i++){
		int u=R[i][0],v=R[i][1],w=L[i];
		adj[u].pb(mp(v,w));
		adj[v].pb(mp(u,w));
	}
	priority_queue<PII,vector<PII>,greater<PII> >q;
	memset(dis,127,sizeof dis);
	for(int i=0;i<k;i++){
		int x=P[i];q.push(mp(0,x));
		dis[x][0]=0;vis[x]++;
	}	
	while(q.size()){
		PII go=q.top();
		int nd=go.ss,val=go.ff;
		q.pop();vis[nd]++;
		if(vis[nd]!=2) continue;
		if(nd==0 and vis[nd]==2)
			return dis[0][1];
		tr(it,adj[nd]){
			int x=it->ff;
			int way=val+it->ss;
			if(vis[x]<2 and way<dis[x][1]){
				dis[x][1]=way;
				if(dis[x][1]<dis[x][0])
					swap(dis[x][1],dis[x][0]);
				q.push(mp(way,x));	
			}
		}
	}
  	return 0;
}

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