oj.uz

Submission #651337

# Submission time Handle Problem Language Result Execution time Memory
651337 2022-10-18T13:19:44 Z therealpain Dreaming (IOI13_dreaming) C++14
32 / 100
 93 ms 13004 KB 
#include "dreaming.h"
#include <bits/stdc++.h> 
#define fi first 
#define se second
#define mp make_pair
#define getbit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
#define TASK "DREAMING"
 
using namespace std;
 
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
 
const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 7;

long long dp[N][2], g[N], d[N], ans;
pair <long long, int> center_dist;
vector <pair <int, int>> a[N];
bool visited[N];
int n, m, l;

void dfs1(int u, int p) {
	visited[u] = 1;
	for (auto i : a[u]) {
		if (i.fi == p) continue;
		int v = i.fi, w = i.se;
		dfs1(v, u);
		if (dp[u][0] < dp[v][0] + w) {
			dp[u][1] = dp[u][0];
			dp[u][0] = dp[v][0] + w;
		} else if (dp[v][0] + w > dp[u][1]) 
			dp[u][1] = dp[v][0] + w; 
	}
	maxi(ans, dp[u][0] + dp[u][1]);
}

void dfs2(int u, int p, long long w) {
	if (p != u) g[u] = max(g[p] + w, (dp[u][0] + w == dp[p][0] ? (dp[p][1] + w) : dp[p][0]));
	mini(center_dist, mp(max(g[u], dp[u][0]),  u));
	for (auto i : a[u]) {
		if (i.fi == p) continue;
		int v = i.fi, w2 = i.se;
		dfs2(v, u, w2); 
	} 
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N;
    m = M;
    l = L;
	for (int i = 0; i < m; ++i) {
		int u = ++A[i], v = ++B[i], w = T[i]; 
		a[u].push_back({v, w});
		a[v].push_back({u, w});
	}
	vector <pair <long long, int>> v;
	for (int i = 1; i <= n; ++i) {
		if (visited[i] == 1) continue;
		dfs1(i, i);
		center_dist = mp(1e9 + 9, 0); 
		dfs2(i, i, 0);
		v.push_back(center_dist);
	}
	sort(all(v), greater <pair <long long, int>>());
	for (int i = 1; i < v.size(); ++i) {
		a[v[0].se].emplace_back(v[i].se, l);
		a[v[i].se].emplace_back(v[0].se, l);
	}
	memset(dp, 0, sizeof dp);
	ans = 0;
	dfs1(1, 1);
	return ans;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i = 1; i < v.size(); ++i) {
      |                  ~~^~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13004 KB Output is correct
2 Correct 59 ms 12560 KB Output is correct
3 Correct 46 ms 11272 KB Output is correct
4 Correct 8 ms 5460 KB Output is correct
5 Correct 8 ms 4948 KB Output is correct
6 Correct 14 ms 6040 KB Output is correct
7 Correct 3 ms 4180 KB Output is correct
8 Correct 30 ms 7796 KB Output is correct
9 Correct 38 ms 9772 KB Output is correct
10 Correct 3 ms 4308 KB Output is correct
11 Correct 55 ms 10344 KB Output is correct
12 Correct 93 ms 11576 KB Output is correct
13 Correct 3 ms 4308 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 3 ms 4180 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Correct 4 ms 4132 KB Output is correct
6 Incorrect 3 ms 4180 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13004 KB Output is correct
2 Correct 59 ms 12560 KB Output is correct
3 Correct 46 ms 11272 KB Output is correct
4 Correct 8 ms 5460 KB Output is correct
5 Correct 8 ms 4948 KB Output is correct
6 Correct 14 ms 6040 KB Output is correct
7 Correct 3 ms 4180 KB Output is correct
8 Correct 30 ms 7796 KB Output is correct
9 Correct 38 ms 9772 KB Output is correct
10 Correct 3 ms 4308 KB Output is correct
11 Correct 55 ms 10344 KB Output is correct
12 Correct 93 ms 11576 KB Output is correct
13 Correct 3 ms 4308 KB Output is correct
14 Correct 3 ms 4180 KB Output is correct
15 Correct 3 ms 4180 KB Output is correct
16 Correct 3 ms 4180 KB Output is correct
17 Correct 3 ms 4180 KB Output is correct
18 Correct 4 ms 4132 KB Output is correct
19 Incorrect 3 ms 4180 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 9728 KB Output is correct
2 Correct 41 ms 9776 KB Output is correct
3 Correct 43 ms 9708 KB Output is correct
4 Correct 45 ms 9816 KB Output is correct
5 Correct 36 ms 9756 KB Output is correct
6 Correct 51 ms 10564 KB Output is correct
7 Correct 47 ms 10064 KB Output is correct
8 Correct 54 ms 9696 KB Output is correct
9 Correct 44 ms 9664 KB Output is correct
10 Correct 49 ms 9896 KB Output is correct
11 Correct 3 ms 4180 KB Output is correct
12 Correct 20 ms 10272 KB Output is correct
13 Correct 19 ms 10336 KB Output is correct
14 Correct 19 ms 10248 KB Output is correct
15 Correct 18 ms 10288 KB Output is correct
16 Correct 17 ms 10128 KB Output is correct
17 Correct 17 ms 9840 KB Output is correct
18 Correct 19 ms 10436 KB Output is correct
19 Correct 19 ms 10172 KB Output is correct
20 Correct 3 ms 4180 KB Output is correct
21 Correct 3 ms 4180 KB Output is correct
22 Correct 4 ms 4436 KB Output is correct
23 Correct 15 ms 10288 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 3 ms 4180 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Correct 4 ms 4132 KB Output is correct
6 Incorrect 3 ms 4180 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13004 KB Output is correct
2 Correct 59 ms 12560 KB Output is correct
3 Correct 46 ms 11272 KB Output is correct
4 Correct 8 ms 5460 KB Output is correct
5 Correct 8 ms 4948 KB Output is correct
6 Correct 14 ms 6040 KB Output is correct
7 Correct 3 ms 4180 KB Output is correct
8 Correct 30 ms 7796 KB Output is correct
9 Correct 38 ms 9772 KB Output is correct
10 Correct 3 ms 4308 KB Output is correct
11 Correct 55 ms 10344 KB Output is correct
12 Correct 93 ms 11576 KB Output is correct
13 Correct 3 ms 4308 KB Output is correct
14 Correct 3 ms 4180 KB Output is correct
15 Correct 3 ms 4180 KB Output is correct
16 Correct 3 ms 4180 KB Output is correct
17 Correct 3 ms 4180 KB Output is correct
18 Correct 4 ms 4132 KB Output is correct
19 Incorrect 3 ms 4180 KB Output isn't correct
20 Halted 0 ms 0 KB -