제출 #226071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226071		cfalas	악어의 지하 도시 (IOI11_crocodile)	C++14	46 / 100	36 ms	48128 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];
map<int, bool> child[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]));
		child[r[i][1]][r[i][0]] = true;
		child[r[i][0]][r[i][1]] = true;
	}
	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=0;i<n;i++){
		if(i) o[i]++;
		o[par[i]]++;
	}
	sort(d.begin(), d.end());
	for(auto x : d){
		//cout<<x.S<<" "<<x.F<<endl;
		int t = x.S;
		bool found = false;
		while(par[t]!=t){
			//cout<<t<<" ";
			if(child[par[t]][t]==false){found=true;break;}
			else if(o[par[t]]>3){ child[par[t]][t]=false, o[par[t]]--; found = true; break;}
			t = par[t];
		}
		//cout<<endl;
		if(!found) return -x.F;
	}
	return -1;
}

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