제출 #226049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226049		cfalas	악어의 지하 도시 (IOI11_crocodile)	C++14	0 / 100	5 ms	384 KiB

crocodile

#include<bits/stdc++.h>
using namespace std;
#include "crocodile.h"
#define F first
#define S second
#define ll long long
typedef pair<ll, ll> ii;
typedef vector<ii> vii;

int dist[1000000];
int par[1000000];
vector<vii> adj;
#define INF 1500000000
bool vis[1000000];
int o[1000000];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	adj.assign(n+1, vii());
	for(int i=0;i<m;i++){
		adj[r[i][0]].push_back(ii(l[i], r[i][1]));
		adj[r[i][1]].push_back(ii(l[i], r[i][0]));
	}
	for(int i=0;i<n;i++){
		sort(adj[i].begin(), adj[i].end());
	}
	priority_queue<ii> q;
	q.push(ii(0, 0));
	dist[0] = 0;
	for(int i=1;i<n;i++) dist[i]=INF;

	while(!q.empty()){
		ii t = q.top();
		q.pop();

		if(-t.F>dist[t.S]) continue;
		//cout<<t.F<<" "<<t.S<<" "<<dist[t.S]<<endl;
		for(auto v : adj[t.S]){
			if(dist[v.S]> -t.F + v.F){
				dist[v.S] = v.F - t.F;
				par[v.S] = t.S;
				q.push(ii(-dist[v.S], v.S));

			}
		}
	}
	vii d;
	for(int i=0;i<k;i++){
		d.push_back(ii(-dist[p[i]], p[i]));
	}
	for(int i=1;i<n;i++){
		o[i]++;
		o[par[i]]++;
	}
	sort(d.begin(), d.end());
	for(auto x : d){
		int t = par[x.S];
		bool found = false;
		while(par[t]!=t){
			if(o[t]>3){ o[t]--; found = true; break;}
			t = par[t];
		}
		if(!found) return -x.F;
	}
	return -1;
}

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