제출 #333023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333023		Cantfindme	꿈 (IOI13_dreaming)	C++17	100 / 100	114 ms	17004 KiB

dreaming

#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
#define ll long long
#define f first
#define s second
typedef pair<int,int> pi;
int INF = 1e9+7;

ll N,E,L;
int visited[100010];
vector <pi> adjlist[100010];
int dist1[100010], dist2[100010];
int camefrom[100010]; 
vector <ll> centerboi; //Stores minimum radius for each tree
int counter=-1;
vector <int> whoishere;
vector <ll> diameters;

void dfsf(int x, int p) {
	whoishere.push_back(x);
	visited[x] = 1;
	for (auto i: adjlist[x]) {
		if (i.f != p) {
			dist1[i.f] = dist1[x] + i.s;
			dfsf(i.f,x);
		}
	}
}

void dfss(int x, int p) {
	camefrom[x] = p;
	for (auto i: adjlist[x]) {
		if (i.f != p) {
			dist2[i.f] = dist2[x] + i.s;
			dfss(i.f,x);
		}
	}
}

void trace(int x,int endn) {
	//~ cout << x << " " << endn << " " << counter << "\n";
	//~ cout << x << " " << dist2[x] << " " << endn << " " << dist2[endn] << "\n";
	if (max(dist2[x],dist2[endn]-dist2[x]) < centerboi[counter]) {
		centerboi[counter] = max(dist2[x],dist2[endn]-dist2[x]);
	}
	//~ cout << centerboi[counter] << "\n";
	if (camefrom[x] != -1) trace(camefrom[x],endn);
}

void rootat(int x) {
	counter++;
	
	whoishere.clear();
	dfsf(x,-1);
	int start = x;
	for (auto i: whoishere) {
		if (dist1[i] > dist1[start]) start = i;
	}
	dfss(start,-1);
	int endn = start;
	for (auto i: whoishere) {
		if (dist2[i] > dist2[endn]) endn = i;
	}
	diameters.push_back(dist2[endn]);
	centerboi.push_back(INF);
	trace(endn,endn);
	//~ cout << counter << " " << start << " " << endn << " " << centerboi[counter] << "\n";
}

int travelTime(int _N, int M, int _L, int A[], int B[], int T[]) {
    N = _N;
    E = M;
    L = _L;
    for (int i =0;i <E;i++) {
		int a = A[i];
		int b = B[i];
		int w = T[i];
		adjlist[a].push_back(pi(b,w));
		adjlist[b].push_back(pi(a,w));
	}
    
    for (int i =0;i<N;i++) if (!visited[i]) rootat(i);
    sort(centerboi.begin(),centerboi.end(),greater<int>());
    //~ cout << "\n";
    //~ for (auto i:centerboi) {
		//~ cout << i << "\n";
	//~ }
	ll ans = 0;
	if (counter >= 1)
		ans = max(ans,centerboi[0] + centerboi[1] + L);
	if (counter >= 2)
		ans = max(ans, centerboi[1] + centerboi[2] + 2*L);
	for (auto i: diameters) {
		ans = max(ans,i);
	}
	return ans;
	
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23