Submission #1211505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211505		moondarkside	Race (IOI11_race)	C++20	0 / 100	0 ms	320 KiB

race

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

struct Node {
	int id;
	int priority;
};
bool operator< (const struct Node& a,const struct Node& b) {
	return a.priority>b.priority;
}

void bfs(int self,int parent,map<int,set<int>>& Roads,priority_queue<struct Node>& Pq) {
	bool ran=true;
	for(int next : Roads[self]) {
		if(next!=parent) {
			ran=false;
			bfs(next,self,Roads,Pq);
		}
	}
	if(Roads[self].size()==1) {
		struct Node a= {self,1};
		Pq.push(a);
	}
	return;
}

int findMidPoint(int base,map<int,set<int>> Roads) {
	std::map<int,int> Value;
	priority_queue<struct Node> Pq;
	bfs(base,-1,Roads,Pq);
	int current=-1;
	while(!Pq.empty()) {
		struct Node currentN=Pq.top();
		current = currentN.id;
		Pq.pop();
		for(int other : Roads[current]) {
			Roads[other].erase(current);
			Value[other]=max(Value[other],1)+currentN.priority;
			if(Roads[other].size()==1) {
				struct Node a= {other,Value[other]};
				Pq.push(a);
			}
		}

	}
	return current;
}

int bfsLen(int self,int parent,int steps,int len,map<int,set<int>>& Roads,map<pair<int,int>,int>& Lenghts,map<int,int>& Bests,
vector<pair<int,int>>& Results,int K,map<int,set<int>>& NewRoads) {

	if(len>K) {
		return -1;
	}

	int bestFN=-1;
	steps++;
	len=len+Lenghts[ {self,parent}];

	if (Bests[K-len]!=0) {
		bestFN= Bests[K-len]-1+steps;
	}

	Results.push_back({len,steps});

	for(int next : Roads[self]) {

		if(next!=parent) {
			NewRoads[next].insert(self);
			NewRoads[self].insert(next);
			int nr=bfsLen(next,self,steps,len,Roads,Lenghts,Bests,Results,K,NewRoads);
			if (nr!=-1) {
				if(bestFN!=-1) {
					bestFN=min(bestFN,nr);
				}
				else {
					bestFN=nr;
				}
			}

		}
	}

	return bestFN;
}

int best_path(int N,int K,int H[][2],int L[]) {
	map<int,set<int>>Road1;
	map<pair<int,int>,int> Lenghts;
	for(int i=0; i<N-1; i++) {
		Lenghts[ {H[i][0],H[i][1]}]=L[i];
		Lenghts[ {H[i][1],H[i][0]}]=L[i];
		Road1[H[i][0]].insert(H[i][1]);
		Road1[H[i][1]].insert(H[i][0]);
	}
	queue<map<int,set<int>>> SubGraphs;
	SubGraphs.push(Road1);
	int best=-1;
	while(!SubGraphs.empty()) {
	    map<int,set<int>>Roads=SubGraphs.front();
	    SubGraphs.pop();
		int split=findMidPoint(0,Roads);
		map<int,int> Best;
		Best[0]=1;
		for(int next:Roads[split]) {
			vector<pair<int,int>> Futurechecks;
			map<int,set<int>>NewRoads;
			int newbest=bfsLen(next,split,0,0,Roads,Lenghts,Best,Futurechecks,K,NewRoads);
			if(newbest!=-1 && (newbest<best||best==-1)) {
				best=newbest;
			}
			if(!NewRoads.empty()){
			   SubGraphs.push(NewRoads); 
			}
			for(int i=0; i<Futurechecks.size(); i++) {
				int len=Futurechecks[i].first;
				int steps=Futurechecks[i].second;
				if(Best[steps]==0) {
					Best[steps]=len+1;
				}
				else {
					Best[steps]=min(Best[steps],len+1);
				}
			}
		}
	}
	return best;
}

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