| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 492569 |
2021-12-08T01:48:10 Z |
uHyHn |
Dreaming (IOI13_dreaming) |
C++14 |
|
119 ms |
16324 KB |
#include<bits/stdc++.h>
//IBOW
#include "dreaming.h"
#define Task "dreaming"
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define rep(i, b) for (int i = (1); i <= (b); ++i)
#define REP(i, b) for (int i = (b); i >= (1); --i)
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<long long> vll;
const int N = 2e5 + 10;
const int inf = 2e9 + 10;
const ll INF = 2e18 + 10;
const int MOD = 1e9 + 7;
int n, m, l, dp[N][2], dp_down[N], cnt = 0, diameter = 0;
vector<ii> g[N];
bool vis[N];
vector<ii> center_node;
void find_center(int u, int p, ii &get_center)
{
if (abs(dp[u][0] - max(dp_down[u], dp[u][1])) < get_center.F)
{
// cout << u << ' ' << abs(dp[u][0] - max(dp_down[u], dp[u][1])) << '\n';
get_center = {abs(dp[u][0] - max(dp_down[u], dp[u][1])), u};
}
for (ii e : g[u])
{
if (e.F == p) continue;
find_center(e.F, u, get_center);
}
}
void dfs(int u, int p = -1)
{
// cout << u << '\n';
vi v;
vis[u] = 1;
dp[u][0] = dp[u][1] = 0;
for (ii e : g[u])
{
if (e.F == p) continue;
dfs(e.F, u);
v.pb(dp[e.F][0] + e.S);
}
sort(all(v), greater<int>());
if (sz(v) >= 2) diameter = max(diameter, v[0] + v[1]);
if (sz(v) >= 1) diameter = max(diameter, v[0]);
for (int i = 0; i < min(2, sz(v)); ++i) dp[u][i] = v[i];
}
void dfs1(int u, int p = -1)
{
for (ii e : g[u])
{
if (e.F == p) continue;
dp_down[e.F] = dp_down[u] + e.S;
if (dp[u][0] == dp[e.F][0] + e.S)
{
dp_down[e.F] = max(dp_down[e.F], dp[u][1] + e.S);
} else
{
dp_down[e.F] = max(dp_down[e.F], dp[u][0] + e.S);
}
dfs1(e.F, u);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
rep(i, m)
{
g[a[i]].pb({b[i], t[i]});
g[b[i]].pb({a[i], t[i]});
}
for (int i = 0; i < n; ++i) if (!vis[i])
{
diameter = 0;
// cnt++;
dfs(i);
dfs1(i);
ii get_center = {inf, -1};
find_center(i, i, get_center);
center_node.pb({diameter, get_center.S});
// cout << i << ' ' << diameter << ' ' << get_center.S << '\n';
}
nth_element(center_node.begin(), center_node.end() - 1, center_node.end());
for (int i = 0; i < sz(center_node) - 1; ++i)
{
// cout << center_node[i].F << ' ' << center_node[i].S << '\n';
g[center_node[i].S].pb({center_node.back().S, l});
g[center_node.back().S].pb({center_node[i].S, l});
}
diameter = 0;
dfs(0);
return diameter;
}
//int32_t main()
//{
// ios_base::sync_with_stdio(false); cin.tie(nullptr);
// if (fopen(Task".in", "r"))
// {
// freopen(Task".in", "r", stdin);
// freopen(Task".out", "w", stdout);
// }
// int t = 1;
// //cin >> t;
// while (t--) DeoAClamcho();
// return 0;
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
16324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
16324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
10936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
16324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
