| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1241813 | Minbaev | Dreaming (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
// #include "dreaming.h"
#include "grader.c"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ar array
#define mrand(a, b) uniform_int_distribution<int>(a, b)(rng)
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace FAST {
template<typename T, typename F>
istream &operator>>(istream &cin, pair<T, F> &p) {
cin >> p.first >> p.second;
return cin;
}
template<typename T, typename F>
ostream &operator<<(ostream &cout, pair<T, F> &p) {
cout << p.first << ' ' << p.second;
return cout;
}
template<typename T>
istream &operator>>(istream &cin, vector<T> &a) {
for (T &i: a) cin >> i;
return cin;
}
template<typename T>
ostream &operator<<(ostream &cout, vector<T> &a) {
for (T i: a) cout << i << ' ';
return cout;
}
template<typename T>
istream &operator>>(istream &cin, deque<T> &a) {
for (T &i: a) cin >> i;
return cin;
}
template<typename T>
ostream &operator<<(ostream &cout, deque<T> &a) {
for (T i: a) cout << i << ' ';
return cout;
}
}
using namespace FAST;
const long long inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int md = 998244353;
vector<ar<int,2>>g[100005], cycle;
vector<int>mx(100005), vis(100005);
void dfs(int x, int pr){
vis[x] = 1;
for(auto [to, cost] : g[x]){
if(to == pr)continue;
dfs(to, x);
umax(mx[x], mx[to] + cost);
}
}
void fmx(int x, int pr, int a){
umax(mx[x], a);
cycle.pb({mx[x], x});
vis[x] = 1;
vector<ar<int,2>>vs;
for(auto [to, cost] : g[x]){
if(to == pr)continue;
vs.pb({mx[to] + cost, to});
}
sort(all(vs));
reverse(all(vs));
// if(x == 1){
// for(auto to:vs)cout << to[0] << " " << to[1] << "\n";
// cout << "\n";
// }
for(auto [to, cost] : g[x]){
if(to == pr)continue;
if(to == vs[0][1]){
if(vs.size() > 1)
fmx(to, x, max(a, vs[1][0]) + cost);
else
fmx(to, x, a + cost);
}
else{
fmx(to, x, max(a, vs[0][0]) + cost);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
// cout << 1 << "\n";
// exit(0);
for(int i = 0;i<M;i++){
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])continue;
dfs(i, -1);
}
// cout << 0 << "\n";
// exit(0);
for(int i = 0;i<N;i++){
vis[i] = 0;
}
vector<ar<int,2>>vs;
// cout << mx[5] << "\n";
for(int i = 0;i<N;i++){
if(vis[i])continue;
cycle.clear();
fmx(i, -1, 0);
sort(all(cycle));
vs.pb({cycle[0][0], cycle[0][1]});
}
sort(all(vs));
reverse(all(vs));
int u = N - M - 1;
int i = 1;
while(u > 0){
u -= 1;
g[vs[0][1]].pb({vs[i][1], L});
g[vs[i][1]].pb({vs[0][1], L});
i += 1;
}
for(int i = 0;i<N;i++){
mx[i] = 0;
vis[i] = 0;
}
dfs(0, -1);
for(int i = 0;i<N;i++){
vis[i] = 0;
}
fmx(0, -1, 0);
return *max_element(all(mx));
}