Submission #1147913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147913		KickingKun	Dreaming (IOI13_dreaming)	C++20	40 / 100	191 ms	131072 KiB

dreaming

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

#define fi first
#define se second

const int LIM = 1e5 + 5;
vector <pair <int, int>> adj[LIM];
int dist[LIM];

void add_edge(int u, int v, int w) {
	adj[u].emplace_back(v, w);
	adj[v].emplace_back(u, w);
//	cerr << u << ' ' << v << ' ' << w << '\n';
}

// sub4
void dfs(int u, int p = -1) {
	for (auto [v, w]: adj[u]) if (v != p) {
		dist[v] = dist[u] + w;
		dfs(v, u);
	}
}
int sub4(int N, int M, int L, int A[], int B[], int T[]) {
	int root = -1, v = -1, ma = 0;
    vector <bool> alone(N, true);
    for (int i = 0; i < M; i++) {
    	if (T[i] > ma) root = A[i], v = B[i], ma = T[i];
    	alone[A[i]] = alone[B[i]] = false;
    }
    
	for (int i = 0; i < M; i++) {
		add_edge(A[i], B[i], T[i]);
	}

    for (int i = 0; i < N; i++) {
		if (alone[i]) add_edge(root, i, L);
	}
	
	for (int i = 0; i < M; i++) {
		if (A[i] != root && B[i] != root)
			add_edge(root, A[i], L);
	}
	
	dfs(root); int leaf = -1, maDis = 0;
	for (int i = 0; i < N; i++)
		if (maDis < dist[i]) {
			maDis = dist[i];
			leaf = i;
		}
	
	dist[leaf] = 0; dfs(leaf);
	return *max_element(dist, dist + N);
}
//

// sub5
int D[3005][3005], f[3005], id[3005];
void findDist(int root, int u, int p) {
	id[u] = id[root];
	for (auto [v, w]: adj[u]) if (v != p) {
		D[root][v] = D[root][u] + w;
		findDist(root, v, u);
	}
}

int sub5(int N, int M, int L, int A[], int B[], int T[]) {
	for (int i = 0; i < M; i++)
		add_edge(A[i], B[i], T[i]);
	
	memset(D, -1, sizeof D);
	memset(id, -1, sizeof id);
	int tree = -1;
	for (int i = 0; i < N; i++) {
		if (id[i] == -1) id[i] = ++tree;
		D[i][i] = 0; findDist(i, i, -1);
		f[i] = *max_element(D[i], D[i] + N);
	}
	
	vector <int> miDist(tree + 1, 2e9), dia(tree + 1, 0);
	for (int i = 0; i < N; i++) {
		miDist[id[i]] = min(miDist[id[i]], f[i]);
		dia[id[i]] = max(dia[id[i]], f[i]);
	}
	
	int init = *max_element(dia.begin(), dia.end());
	// diameter per tree
	
	int ans = 2e9;
	for (int center = 0; center < N; center++) {
		pair <int, int> ma(f[center], 0);
		for (int t = 0; t <= tree; t++) if (t != id[center]) {
			int cur = miDist[t] + L;
			if (cur > ma.fi) ma = make_pair(cur, ma.fi);
			else ma.se = max(ma.se, cur);
		}
		int res = max(init, ma.fi + ma.se);
		ans = min(ans, res);
	}
	return ans;
}
//

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    if (N <= 3000) return sub5(N, M, L, A, B, T);
    else return sub4(N, M, L, A, B, T);
}

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