oj.uz

Submission #304089

# Submission time Handle Problem Language Result Execution time Memory
304089 2020-09-21T02:42:38 Z Fischer Dreaming (IOI13_dreaming) C++14
0 / 100
 202 ms 65540 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 1e5 + 10;
vector<pair<int, int>> g[maxn];
pair<int, int> len[maxn];
vector<int> arr;
bool vis[maxn];
 
void add(int x, int t) {
	if (t >= len[x].first) {
		len[x].second = len[x].first;
		len[x].first = t;
	} else {
		len[x].second = max(len[x].second, t);
	}
}
 
int dfs(int x, int p) {
	vis[x] = 1;
	len[x] = {0, 0};
	for (auto e : g[x]) {
		if (e.first == p) continue;
		dfs(e.first, x);
		add(x, len[e.first].first+e.second);
	}
}
 
int dfs_reroot(int x, int p, int r) {
	if (~p) {
		if (len[p].first == len[x].first+r) {
			add(x, len[p].second+r);
		} else {
			add(x, len[p].first+r);
		}
	}
	int ans = x;
	for (auto e : g[x]) {
		if (e.first == p) continue;
		int v = dfs_reroot(e.first, x, e.second);
		if (len[ans].first > len[v].first) {
			ans = v;
		}
	}
	return ans;
}
 
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i=0; i<N; ++i) g[i].clear(), vis[i] = 0;
	for (int i=0; i<M; ++i) {
		g[A[i]].emplace_back(B[i], T[i]);
		g[B[i]].emplace_back(A[i], T[i]);
	}
	for (int i=0; i<N; ++i) {
		if (vis[i]) continue;
		dfs(i, -1);
		arr.emplace_back(dfs_reroot(i, -1, 0));
	}
	sort(arr.begin(), arr.end(), [&](int x, int y) {
		return len[x].first > len[y].second;
	});
	for (int i = 1; i < arr.size(); ++i) {
		g[arr[0]].emplace_back(arr[i], L);
		g[arr[i]].emplace_back(arr[0], L);
	}
	dfs(0, -1);
	dfs_reroot(0, -1, 0);
	int ans = 0;
	for (int i = 0; i < N; ++i) {
		ans = max(ans, len[i].first);
	}
	return ans;
}

Compilation message

dreaming.cpp: In function 'int dfs(int, int)':
dreaming.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
   28 | }
      | ^
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for (int i = 1; i < arr.size(); ++i) {
      |                  ~~^~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 202 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 202 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 202 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 10112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 202 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 202 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -