Submission #672537

#	Time	Username	Problem	Language	Result	Execution time	Memory
672537		Hacv16	Dreaming (IOI13_dreaming)	C++17	0 / 100	69 ms	61392 KiB

dreaming

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

const int MAX = 2e6 + 15;
const int INF = 0x3f3f3f3f;

#define fr first
#define sc second

int r1, r2, mxdiam, d[MAX], dist[MAX], pai[MAX];
int mx, mxx, id;
bool seen[MAX];
vector<pair<int, int>> adj[MAX];

void dfs(int u, int p, int dt, int dtt, bool f){
	if(dt == mx && dtt > mxx) mxx = dtt, id = u;
	if(dt > mx) id = u, mx = dt, mxx = dtt;
	mxdiam = max(mxdiam, dtt);

	if(f) pai[u] = p, d[u] = dt, dist[u] = dtt; 

	seen[u] = true;

	for(auto e : adj[u]){ 
		int v = e.fr, w = e.sc;
		if(v == p) continue;
		dfs(v, u, dt + 1, dtt + w, f);
	}
}

int getRadius(int u){
	mx = -1; mxx = -1;
	dfs(u, -1, 0, 0, 0);

	int ponta1 = id;
	
	mx = -1; mxx = -1;
	dfs(ponta1, -1, 0, 0, 1);

	int ponta2 = id;
    
    if(ponta1 == ponta2) return 0;
    
	int cur = ponta2;
	vector<int> path;

	while(cur != -1){
		path.push_back(cur);
		cur = pai[cur];
	}

	if(path.size() % 2){
		int cent = path[path.size() / 2];
		return max(dist[cent], dist[ponta2] - dist[cent]);

	}else{
		int cent1 = path[path.size() / 2];
		int cent2 = path[path.size() / 2 - 1];

		int mxr1 = max(dist[cent1], dist[ponta2] - dist[cent1]);
		int mxr2 = max(dist[cent2], dist[ponta2] - dist[cent2]);

		if(mxr1 <= mxr2) return mxr1;
		return mxr2;
	}

	return -INF;
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]){
	for(int i = 0; i < m; i++){
		int u = A[i], v = B[i], w = T[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}

	for(int i = 0; i < n; i++){
		if(seen[i]) continue;
		int r = getRadius(i);
		
		if(r > r1){ swap(r1, r2); r1 = r; }
		else if(r > r2) { r2 = r; }
	}
	
	return max(mxdiam, L + r1 + r2);
}

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