Submission #308225

#	Time	Username	Problem	Language	Result	Execution time	Memory
308225		sofapuden	Traffic (IOI10_traffic)	C++14	50 / 100	669 ms	139744 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

vector<vector<int>> gra;
vector<int> we, rou;
priority_queue<pair<pair<int,int>,int>, vector<pair<pair<int,int>,int>>, greater<pair<pair<int,int>,int>>> Q;

int dfs(int x, int p, int t){
	if(t == x){
		rou.push_back(x);
		return 1;
	}
	for(auto y : gra[x]){
		if(y == p)continue;
		if(dfs(y,x,t)){
			rou.push_back(x);
			return 1;
		}
	}
	return 0;
}
		
int dfs2(int x, int p1, int p2){
	int sum = we[x];
	for(auto y : gra[x]){
		if(y == p1 || y == p2)continue;
		sum+=dfs2(y,x,x);
	}
	return sum;
}

void bfs(pair<pair<int,int>,int> node){
	for(auto x : gra[node.f.s]){
		if(node.s == x)continue;
		Q.push({{node.f.f+we[x],x},node.f.s});
	}
}

int LocateCentre(int n, int pp[], int s[], int d[]) {
	if(n == 1)return 0;
	gra.resize(n);
	for(int i = 0; i < n; ++i){
		we.push_back(pp[i]);
	}
	for(int i = 0; i < n-1; i++){
		gra[s[i]].push_back(d[i]);
		gra[d[i]].push_back(s[i]);
	}
	Q.push({{we[0],0},0});
	pair<pair<int,int>,int> firs,last;
	while(!Q.empty()){
		auto x = Q.top();
		Q.pop();
		firs = x;
		bfs(x);
	}
	Q.push({{we[firs.f.s],firs.f.s},firs.f.s});
	while(!Q.empty()){
		auto x = Q.top();
		Q.pop();
		last = x;
		bfs(x);
	}
	dfs(firs.f.s, firs.f.s, last.f.s);
	int maxi = we[rou[0]]+we[rou[(int)rou.size()-1]];
	for(int i = 1; i < (int)rou.size()-1; ++i){
		we[rou[i]] = dfs2(rou[i],rou[i-1],rou[i+1]);
		maxi+=we[rou[i]];
	} 
	pair<int,int> best = {maxi,-1};
	int c1 = 0, c2 = best.f;
	for(int i = 0; i < (int)rou.size(); ++i){
		if(i)c1+=we[rou[i-1]];
		c2-=we[rou[i]];
		if(best.f > max(c1,c2)){
			best = make_pair(min(best.f,max(c1,c2)),rou[i]);
		}
	}
	return best.s;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25