제출 #1214231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214231		moondarkside	Race (IOI11_race)	C++20	21 / 100	3091 ms	27328 KiB

race

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int n,k;
map<int,std::vector<std::pair<int, int>>> Roads;
vector<bool> Visited;
priority_queue<struct PriorityPoint> EdgePriority;
vector<pair<int,int>>Steps;
map<int,int> Win;
bool Unit;

struct PriorityPoint {
	int id;
	int priority;
};

bool operator< (const struct PriorityPoint& a,const struct PriorityPoint& b) {
	return b.priority<a.priority;
}

void bfsFindEdges(int parent,int current) {
	int exec=0;
	for(int i=0; i<Roads[current].size(); i++) {
		int next=Roads[current][i].first;
		if(Visited[next]==false) {
			exec++;
			if(parent!=next) {
				bfsFindEdges(current,next);
			}
		}
	}
	if(exec==0) {
		Unit=true;
	}
	if(exec==1) {
		EdgePriority.push({current,1});
	}
	return;
}

int GetCentriod(int base) {
	EdgePriority=priority_queue <struct PriorityPoint>();
	Unit=false;
	bfsFindEdges(-1,base);

	if(Unit) {
		return -1;

	}

	int last=0;
	map<int, int> TimesVisited;
	map<int,int> Value;
    int iter=0;
	while(!EdgePriority.empty() && iter<100000) {
        iter++;
		int me=EdgePriority.top().id;
		TimesVisited[me]=-1000000;
		last=me;

		for(int i=0; i<Roads[me].size(); i++) {
		    int other=Roads[me][i].first;
			if(Visited[other]==false) {

				
				Value[other]=(Value[other]+EdgePriority.top().priority);
				TimesVisited[other]=TimesVisited[other]+1;

				if(TimesVisited[other]+1==Win[other]) {
					EdgePriority.push({other,Value[other]+1});

				}
			}

		}
		EdgePriority.pop();
	}

	return last;

}

void bfsGetDistance(int parent,int base,int steps,int lenght) {
    
	  Steps.push_back({lenght,steps});

	for(int i=0; i<Roads[base].size(); i++) {
		int next=Roads[base][i].first;
		if(Visited[next]==false) {

			if(parent!=next) {
				bfsGetDistance(base,next,steps+1,lenght+Roads[base][i].second);
			}
		}
	}

}


int bestPathFrom(int base) {
	int res=100000000;
	int centroid=GetCentriod(base);

	if(centroid==-1) {
		Visited[base]=true;
		return 100000000;
	}

	Visited[centroid]=true;


	map<int,int> Best;
	Best[0]=1;

	for(int i=0; i<Roads[centroid].size(); i++) {

        int next=Roads[centroid][i].first;

		if(Visited[next]==false) {
			Steps.clear();
			
			Win[next]=Win[next]-1;
			bfsGetDistance(centroid,Roads[centroid][i].first,1,Roads[centroid][i].second);
			for(int i=0; i<Steps.size(); i++) {
				int len=Steps[i].first;
				if(Best[k-len]>0) {
					res=min(Best[k-len]+Steps[i].second-1,res);
				}

			}

			for(int i=0; i<Steps.size(); i++) {
				int len=Steps[i].first;
				if(Best[len]==0) {
					Best[len]=Steps[i].second+1;
				}
				else {
					Best[len]=min(Best[len],Steps[i].second+1);
				}

			}
		}

	}

	for(int i=0; i<Roads[centroid].size(); i++) {
	    int next=Roads[centroid][i].first;
		if(Visited[next]==false) {
			res=min(res,bestPathFrom(next));
		}
	}

	return res;
}

int best_path(int N,int K,int H[][2],int L[] ) {
	n=N;
	k=K;
	Visited.push_back(false);
	for(int i=0; i<N-1; i++) {
		Visited.push_back(false);

		Win[H[i][0]]=Win[H[i][0]]+1;
		Win[H[i][1]]=Win[H[i][1]]+1;


        int a=H[i][0];
        int b=H[i][1];
		Roads[a].push_back({b,L[i]});
		Roads[b].push_back({a,L[i]});
	}

	int ret=bestPathFrom(0);

	if(ret==100000000) {
		return -1;
	}

	return ret;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57