oj.uz

Submission #211196

# Submission time Handle Problem Language Result Execution time Memory
211196 2020-03-19T11:54:15 Z mode149256 Dreaming (IOI13_dreaming) C++14
18 / 100
 71 ms 12152 KB 
/*input

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

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

vb been;
int last;
int longest;
int puse;
vpi edges[MX];

void dfs(int x, int prev, int dis) {
	if (dis > longest) {
		longest = dis;
		last = x;
	}

	for (auto u : edges[x])
		if (u.x != prev)
			dfs(u.x, x, dis + u.y);
}

void dfs(int x) {
	been[x] = true;
	for (auto u : edges[x])
		if (!been[u.x])
			dfs(u.x);
}

bool raskPuse(int x, int prev, int dis) {
	if (dis == longest) return true;
	bool kely = false;

	for (auto u : edges[x])
		if (u.x != prev)
			kely = kely || raskPuse(u.x, x, dis + u.y);

	if (kely) puse = min(puse, max(dis, longest - dis));
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	been = vb(N, false);

	for (int i = 0; i < M; ++i)
	{
		edges[A[i]].emplace_back(B[i], T[i]);
		edges[B[i]].emplace_back(A[i], T[i]);
	}

	vi puses;
	int ats = 0;

	for (int i = 0; i < N; ++i)
	{
		if (been[i]) continue;
		longest = 0;
		last = i;
		dfs(i, -1, 0);
		longest = 0;
		dfs(last, -1, 0);

		puse = longest;
		ats = max(ats, longest);

		raskPuse(last, -1, 0);

		puses.emplace_back(puse);

		dfs(i);
		// printf("i = %d, longest = %d, puse = %d\n", i, longest, puse);
	}

	sort(puses.rbegin(), puses.rend());

	if (puses.size() >= 2) {
		ats = max(ats, puses[0] + L + puses[1]);
	}

	if (puses.size() >= 3) {
		ats = max(ats, puses[1] + L + L + puses[2]);
	}

	return ats;
}

Compilation message

dreaming.cpp: In function 'bool raskPuse(int, int, int)':
dreaming.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 12152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 12152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 12152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5888 KB Output is correct
2 Correct 31 ms 5888 KB Output is correct
3 Correct 30 ms 5888 KB Output is correct
4 Correct 28 ms 5880 KB Output is correct
5 Correct 28 ms 5888 KB Output is correct
6 Correct 30 ms 6264 KB Output is correct
7 Correct 33 ms 6012 KB Output is correct
8 Correct 29 ms 5760 KB Output is correct
9 Correct 31 ms 5752 KB Output is correct
10 Correct 30 ms 5888 KB Output is correct
11 Correct 6 ms 2688 KB Output is correct
12 Correct 9 ms 3320 KB Output is correct
13 Correct 10 ms 3324 KB Output is correct
14 Correct 9 ms 3324 KB Output is correct
15 Correct 9 ms 3324 KB Output is correct
16 Correct 10 ms 3324 KB Output is correct
17 Correct 9 ms 3324 KB Output is correct
18 Correct 9 ms 3452 KB Output is correct
19 Correct 9 ms 3452 KB Output is correct
20 Correct 6 ms 2688 KB Output is correct
21 Correct 6 ms 2688 KB Output is correct
22 Correct 6 ms 2688 KB Output is correct
23 Correct 9 ms 3452 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 12152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 12152 KB Output isn't correct
2 Halted 0 ms 0 KB -