oj.uz

Submission #163533

# Submission time Handle Problem Language Result Execution time Memory
163533 2019-11-13T18:16:05 Z kostia244 Dreaming (IOI13_dreaming) C++17
18 / 100
 117 ms 13816 KB 
#include "dreaming.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pi = pair<ll, ll>;
const int maxn = 100100;
int n;
vector<pi> g[maxn];
pi dp[maxn];
int vis[maxn];
ll d;
void dfs(int v) {
	ll x, y;
	x=y=0;
	vis[v] = 1;
	for(auto i: g[v]) {
		if(vis[i.first]) continue;
		dfs(i.first);
		ll t = i.second + dp[i.first].first;
		if(x<t) y = x, x = t;
		else if(y < t) y = t;
	}
	dp[v] = {x, y};
}
void findd(int v, int p, ll len = 0) {
	d = min(d, max(len, dp[v].first));
	for(auto i : g[v]) {
		if(i.first==p) continue;
		ll x = len+i.second;
		if(dp[i.first].first+i.second!=dp[v].first) x = max(x, dp[v].first+i.second);
		else x = max(x, dp[v].second+i.second);
		findd(i.first, v, x);
	}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N;
	if(n==1) return 0;
	for(int i = 0; i < M; i++) {
		g[A[i]].pb({B[i], T[i]});
		g[B[i]].pb({A[i], T[i]});
	}
	vector<ll> x;
	for(int i = 0; i < n; i++) {
		if(vis[i]) continue;
		dfs(i);
		d = 1e17;
		findd(i, i);
		x.pb(d);
	}
	sort(x.rbegin(), x.rend());
	ll ans = x[0];
	if(x.size()>1) ans = max(ans, x[0]+L+x[1]);
	if(x.size()>2) ans = max(ans, x[2]+L+L+x[1]);
    return ans;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 13816 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 30 ms 7544 KB Output is correct
2 Correct 33 ms 7900 KB Output is correct
3 Correct 32 ms 7928 KB Output is correct
4 Correct 33 ms 7924 KB Output is correct
5 Correct 33 ms 7964 KB Output is correct
6 Correct 35 ms 8692 KB Output is correct
7 Correct 34 ms 8184 KB Output is correct
8 Correct 30 ms 7800 KB Output is correct
9 Correct 36 ms 7924 KB Output is correct
10 Correct 31 ms 8052 KB Output is correct
11 Correct 4 ms 2680 KB Output is correct
12 Correct 10 ms 5616 KB Output is correct
13 Correct 10 ms 5744 KB Output is correct
14 Correct 10 ms 5616 KB Output is correct
15 Correct 10 ms 5616 KB Output is correct
16 Correct 10 ms 5612 KB Output is correct
17 Correct 10 ms 5608 KB Output is correct
18 Correct 11 ms 5872 KB Output is correct
19 Correct 10 ms 5616 KB Output is correct
20 Correct 4 ms 2680 KB Output is correct
21 Correct 4 ms 2680 KB Output is correct
22 Correct 4 ms 2808 KB Output is correct
23 Correct 11 ms 5556 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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