Submission #658794

#	Time	Username	Problem	Language	Result	Execution time	Memory
658794		Markomafko972	Dreaming (IOI13_dreaming)	C++14	100 / 100	99 ms	25568 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

vector< pair<int, int> > v[100005];
int bio[100005];
int prt[100005];
int g[100005];
int da[100005];
vector<int> sol;
vector<int> dj;

int rek(int x, int p) {
	da[x] = 1;

	int rj = max(bio[x], g[x]);
	for (int i = 0; i < (int)v[x].size(); i++) {
		if (v[x][i].X != p) {
			rj = min(rj, rek(v[x][i].X, x));
		}
	}
	return rj;
}

int dfs(int x, int p) {
	bio[x] = 0;
	prt[x] = p;

	for (int i = 0; i < (int)v[x].size(); i++) {
		if (v[x][i].X != p) bio[x] = max(bio[x], dfs(v[x][i].X, x)+v[x][i].Y);
	}

	return bio[x];
}

void dfs2(int x, int p) {
	vector<int> tren;
	for (int i = 0; i < (int)v[x].size(); i++) {
		if (v[x][i].X != p) tren.push_back(bio[v[x][i].X]+v[x][i].Y);
	}
	sort(tren.begin(), tren.end());

	int post = 1;
	if (p == -1) post = 0;
	if ((int)tren.size() >= 2) {
		for (int i = 0; i < (int)v[x].size(); i++) {
			if (v[x][i].X != p) {
				int pos =(int)tren.size()-1;
				if (tren[pos] == bio[v[x][i].X]+v[x][i].Y) pos--;
				g[v[x][i].X] = max(tren[pos]+v[x][i].Y, g[x]+v[x][i].Y);
			}
		}
	}
	else if ((int)tren.size() == 1) {
		if (v[x][0].X != p) g[v[x][0].X] = g[x]+v[x][0].Y;
		else g[v[x][1].X] = g[x]+v[x][1].Y;
	}

	for (int i = 0; i < (int)v[x].size(); i++) {
		if (v[x][i].X != p) dfs2(v[x][i].X, x);
	}
}

int travelTime(int n, int m, int l, int a[], int b[], int c[]) {
	for (int i = 0; i < m; i++) {
		v[a[i]].push_back({b[i], c[i]});
		v[b[i]].push_back({a[i], c[i]});
	}

	memset(bio, -1, sizeof bio);
	for (int i = 0; i < n; i++) {
		if (bio[i] == -1) {
			dfs(i, -1);
			dfs2(i, -1);
		}
	}

	for (int i = 0; i < n; i++) {
		if (da[i] == 0) sol.push_back(rek(i, -1));
	}

	int out = 0;
	sort(sol.begin(), sol.end());
	if (sol.size() >= 2) out = max(out, sol.back()+l+sol[(int)sol.size()-2]);
	if (sol.size() >= 3) out = max(out, sol[(int)sol.size()-2]+2*l+sol[(int)sol.size()-3]);
	
	for (int i = 0; i < n; i++) {
		dj.clear();
		for (int j = 0; j < (int)v[i].size(); j++) {
			if (v[i][j].X != prt[i]) dj.push_back(bio[v[i][j].X]+v[i][j].Y);
		}
		sort(dj.begin(), dj.end());
		reverse(dj.begin(), dj.end());

		if ((int)dj.size() >= 2) out = max(out, dj[0]+dj[1]);
		if (prt[i] != -1) out = max(out, bio[i]+g[i]);
	}

	return out;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:45:6: warning: variable 'post' set but not used [-Wunused-but-set-variable]
   45 |  int post = 1;
      |      ^~~~

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