Submission #1012586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012586		AmirAli_H1	Dreaming (IOI13_dreaming)	C++17	100 / 100	67 ms	24480 KiB

dreaming

// In the name of Allah
 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
 
typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;
 
#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n, m, W;
const int maxn = 2e5 + 7;
const int oo = 1e9 + 7;
vector<pii> adj[maxn];
vector<int> ls; int res;
int h[maxn], D1[maxn], D2[maxn];
int mark[maxn], col[maxn], c;
vector<int> A[maxn];
 
void dfs(int v) {
	mark[v] = 1; col[v] = c; A[c].pb(v);
	for (auto f : adj[v]) {
		int u = f.F, w = f.S;
		if (!mark[u]) {
			dfs(u);
		}
	}
}
 
void cal_dfs(int v, int p = -1) {
	if (p == -1) h[v] = 0;
	for (auto f : adj[v]) {
		int u = f.F, w = f.S;
		if (u == p) continue;
		h[u] = h[v] + w;
		cal_dfs(u, v);
	}
}
 
int cal_dis(int c) {
	int v = A[c][0];
	cal_dfs(v);
	
	int u1 = A[c][0];
	for (int r : A[c]) {
		if (h[r] > h[u1]) u1 = r;
	}
	cal_dfs(u1);
	for (int r : A[c]) D1[r] = h[r];
	
	int u2 = A[c][0];
	for (int r : A[c]) {
		if (h[r] > h[u2]) u2 = r;
	}
	cal_dfs(u2);
	for (int r : A[c]) {
		D2[r] = h[r];
		res = max(res, h[r]);
	}
	
	int mn = oo;
	for (int r : A[c]) {
		mn = min(mn, max(D1[r], D2[r]));
	}
	return mn;
}
 
int travelTime(int Nx, int Mx, int Lx, int Ax[], int Bx[], int Tx[]) {
	n = Nx; m = Mx; W = Lx;
	for (int i = 0; i < m; i++) {
		int u = Ax[i], v = Bx[i], w = Tx[i];
		adj[u].pb(Mp(v, w)); adj[v].pb(Mp(u, w));
	}
	
	res = 0;
	for (int i = 0; i < n; i++) {
		if (!mark[i]) {
			dfs(i);
			ls.pb(cal_dis(c)); c++;
		}
	}
	sort(all(ls), greater<int>());
	
	if (len(ls) >= 2) res = max(res, ls[0] + ls[1] + W);
	if (len(ls) >= 3) res = max(res, ls[1] + ls[2] + 2 * W);
	return res;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int)':
dreaming.cpp:38:16: warning: unused variable 'w' [-Wunused-variable]
   38 |   int u = f.F, w = f.S;
      |                ^

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