oj.uz

Submission #897757

# Submission time Handle Problem Language Result Execution time Memory
897757 2024-01-03T16:07:17 Z aqxa Dreaming (IOI13_dreaming) C++17
10 / 100
 1000 ms 26960 KB 
#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"

using ll = long long; 

const int N = 1e5; 

#define fs first
#define sc second
#define mp make_pair

vector<pair<int, int>> g[N]; 
int vis[N], mxd[N], mx[N]; 
multiset<int> ms[N]; 

void dfs(int x, int p) {
	vis[x] = 1; 
	for (auto [u, w]: g[x]) {
		if (u != p) {
			dfs(u, x); 
			mxd[x] = max(mxd[x], mxd[u] + w);
		}
	}
}
void dfs2(int x, int p, int f) {
	ms[x].insert(f); 
	for (auto [u, w]: g[x]) {
		if (u != p) {
			ms[x].insert(mxd[u] + w); 
		}
	}
	mx[x] = *(ms[x].rbegin()); 
	for (auto [u, w]: g[x]) {
		if (u != p) {
			ms[x].erase(ms[x].lower_bound(mxd[u] + w)); 
			dfs2(u, x, *(ms[x].rbegin()) + w); 
			ms[x].insert(mxd[u] + w); 
		}
	}
}
int dfs3(int x, int p) {
	int res = mx[x]; 
	for (auto [u, w]: g[x]) {
		if (u == p) continue; 
		res = min(res, dfs3(u, x)); 
	}
	return res; 
}

int dbg[N]{ 0 }; 
int slow(int x, int p) {
	int mx = 0; 
	for (auto [u, w]: g[x]) {
		if (u != p) {
			mx = max(mx, slow(u, x) + w); 
		}
	}
	return mx; 
}

int travelTime(int n, int m, int l, int u[], int v[], int t[]){
	for (int i = 0; i < n; ++i) {
		vis[i] = 0; 
		mxd[i] = 0; 
		mx[i] = 0; 
	}
	for (int i = 0; i < m; ++i) {
		g[u[i]].push_back(mp(v[i], t[i])); 
		g[v[i]].push_back(mp(u[i], t[i])); 
	}

	vector<int> mxdist; 
	for (int i = 0; i < n; ++i) {
		if (!vis[i]) {
			dfs(i, -1); 
			dfs2(i, -1, 0); 
			mxdist.push_back(dfs3(i, -1)); 
		}
	}
	for (int i = 0; i < n; ++i) {
		assert(slow(i, -1) == mx[i]); 
	}
	sort(mxdist.begin(), mxdist.end()); 
	
	int ans = 0; 
	for (int i = 0; i < n; ++i) {
		ans = max(ans, mx[i]); 
	}

	int sz = (int) mxdist.size(); 
	assert(sz > 0); 
	if (sz == 1) {
		assert(m + 1 == n); 
	} else {
		ans = max(ans, mxdist[sz - 1] + mxdist[sz - 2] + l); 
	}

	// for (int i = 0; i < n; ++i) {
	// 	cout << "! " << i << ' ' << mx[i] << '\n';
	// }

  	return ans; 
}


// int32_t main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);

// 	int nn = 4, M = 2, L = 2; 
// 	int A[]{1, 0};//{0,8,2,5,5,1,1,10};
// 	int B[]{2, 4};//{8,2,7,11,1,3,9,6}; 
// 	int C[]{1000, 2000};//{4,2,4,3,7,1,5,3};
	
// 	cout << "answer: " << travelTime(nn, M, L, A, B, C); 

// 	return 0; 
// }

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 26960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9816 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 10032 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 3 ms 9820 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 2 ms 9820 KB Output is correct
23 Correct 2 ms 10048 KB Output is correct
24 Correct 2 ms 9820 KB Output is correct
25 Correct 2 ms 9820 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 26960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 18132 KB Output is correct
2 Incorrect 27 ms 18124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9816 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 10032 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 3 ms 9820 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 2 ms 9820 KB Output is correct
23 Correct 2 ms 10048 KB Output is correct
24 Correct 2 ms 9820 KB Output is correct
25 Correct 2 ms 9820 KB Output is correct
26 Correct 3 ms 10072 KB Output is correct
27 Correct 3 ms 10076 KB Output is correct
28 Correct 4 ms 10332 KB Output is correct
29 Correct 3 ms 10076 KB Output is correct
30 Correct 3 ms 10076 KB Output is correct
31 Correct 4 ms 10332 KB Output is correct
32 Incorrect 3 ms 10076 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 26960 KB Time limit exceeded
2 Halted 0 ms 0 KB -