| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 940228 | shenfe1 | Dreaming (IOI13_dreaming) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma optimize("Ofast")
#pragma target("avx2")
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
// #define int ll
const int MAX=1e5+15;
const ll inf=1e9;
const int mod=1e9+7;
const int mod1=1e9+9;
const ld eps=1e-9;
int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
int binpow(int a,int n){
if(!n)return 1;
if(n%2==1)return a*binpow(a,n-1);
int k=binpow(a,n/2);
return k*k;
}
#include "dreaming.h"
int n;
int tin[MAX],tout[MAX],timer;
int use[MAX];
int d[MAX];
int rev[MAX];
vector<pii> g[MAX];
vector<int> vec;
void dfs1(int v){
vec.pb(v);
use[v]=1;
for(auto to:g[v]){
if(!use[to.F])dfs1(to.F);
}
}
void dfs(int v,int p=-1){
tin[v]=++timer;
rev[timer]=v;
for(auto to:g[v]){
if(to.F!=p){
d[to.F]=d[v]+to.S;
dfs(to.F,v);
}
}
tout[v]=timer;
}
int t[4*MAX],add[4*MAX];
int C;
void build(int v,int tl,int tr){
add[v]=0;
if(tl==tr){
t[v]=d[rev[tl]];
return;
}
int tm=(tl+tr)/2;
build(2*v,tl,tm);
build(2*v+1,tm+1,tr);
t[v]=max(t[2*v],t[2*v+1]);
}
void push(int v){
add[2*v]+=add[v];
add[2*v+1]+=add[v];
t[2*v]+=add[v];
t[2*v+1]+=add[v];
add[v]=0;
}
void update(int v,int tl,int tr,int l,int r,int x){
if(l>r||tl>r||l>tr)return;
if(l<=tl&&tr<=r){
t[v]+=x;
add[v]+=x;
return;
}
int tm=(tl+tr)/2;
push(v);
update(2*v,tl,tm,l,r,x);
update(2*v+1,tm+1,tr,l,r,x);
t[v]=max(t[2*v],t[2*v+1]);
}
ll calc(int v,int p=-1){
ll ans=t[1];
// cout<<v<<" "<<t[1]<<"\n";
for(auto to:g[v]){
if(to.F==p)continue;
update(1,1,C,tin[to.F],tout[to.F],-to.S);
update(1,1,C,1,tin[to.F]-1,to.S);
update(1,1,C,tout[to.F]+1,C,to.S);
ans=min(ans,calc(to.F,v));
update(1,1,C,tin[to.F],tout[to.F],to.S);
update(1,1,C,1,tin[to.F]-1,-to.S);
update(1,1,C,tout[to.F]+1,C,-to.S);
}
// cout<<v<<" "<<ans<<" "<<t[1]<<"\n";
return ans;
}
int diam(vector<int> ver){
dfs(ver[0]);
int c=ver[0];
for(int x:ver){
if(d[c]<d[x])c=x;
}
for(int x:ver)d[x]=0;
dfs(c);
int ans=0;
for(int x:ver){
ans=max(ans,d[x]);
}
return ans;
}
int solve(vector<int> ver){
int f=diam(ver);
{
timer=0;
mem(rev,0);
mem(d,0);
dfs(ver[0]);
}
C=sz(ver);
build(1,1,C);
// for(int i=1;i<=n;i++)cout<<rev[i]<<" ";
// cout<<"\n";
return max(f,calc(ver[0]));
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
assert(M==N-2);
n=N;
for(int i=0;i<M;i++){
g[A[i]+1].pb({B[i]+1,T[i]});
g[B[i]+1].pb({A[i]+1,T[i]});
}
ll ans=L;
for(int i=1;i<=n;i++){
if(!use[i]){
dfs1(i);
ans+=solve(vec);
vec.clear();
}
}
return ans;
}