Submission #338457

#	Time	Username	Problem	Language	Result	Execution time	Memory
338457		nandonathaniel	Dreaming (IOI13_dreaming)	C++14	100 / 100	200 ms	20076 KiB

dreaming

#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> pii;
const int MAXN=100005;

vector<pii> adj[MAXN];
vector<int> component;
int idx,jarak[MAXN],tree[4*MAXN],lazy[4*MAXN],ST[MAXN],EN[MAXN],preorder[MAXN];
bool visited[MAXN];

void dfs(int now,int par,int dist){
	visited[now]=true;
	idx++;
	ST[now]=idx;
	jarak[now]=dist;
	preorder[idx]=now;
	for(auto nxt : adj[now]){
		if(nxt.first==par)continue;
		dfs(nxt.first,now,dist+nxt.second);
	}
	EN[now]=idx;
}

void updatenode(int now,int L,int R,int val){
	tree[now]+=val;
	lazy[now]+=val;
}
 
void pushdown(int now,int L,int R){
	int mid=(L+R)/2;
	updatenode(2*now,L,mid,lazy[now]);
	updatenode(2*now+1,mid+1,R,lazy[now]);
	lazy[now]=0;
}
 
void build(int now,int L,int R){
	lazy[now]=0;
	if(L==R){
		tree[now]=jarak[preorder[L]];
		return;
	}
	int mid=(L+R)/2;
	build(2*now,L,mid);
	build(2*now+1,mid+1,R);
	tree[now]=max(tree[2*now],tree[2*now+1]);
}

void update(int now,int L,int R,int x,int y,int val){
	if(L>=x && R<=y){
		updatenode(now,L,R,val);
		return;
	}
	if(L>y || R<x)return;
	pushdown(now,L,R);
	int mid=(L+R)/2;
	update(2*now,L,mid,x,y,val);
	update(2*now+1,mid+1,R,x,y,val);
	tree[now]=max(tree[2*now],tree[2*now+1]);
}
 
int query(int now,int L,int R,int x,int y){
	if(L>=x && R<=y)return tree[now];
	if(L>y || R<x)return 0;
	pushdown(now,L,R);
	int mid=(L+R)/2;
	return max(query(2*now,L,mid,x,y),query(2*now+1,mid+1,R,x,y));
}

int furthest,diameter;

void dfsR(int now,int par){
	int leafTerjauh=query(1,1,idx,1,idx);
	furthest=min(furthest,leafTerjauh);
	diameter=max(diameter,leafTerjauh);
	for(auto nxt : adj[now]){
		if(nxt.first==par)continue;
		update(1,1,idx,1,idx,nxt.second);
		update(1,1,idx,ST[nxt.first],EN[nxt.first],-2*nxt.second);
		dfsR(nxt.first,now);
		update(1,1,idx,1,idx,-nxt.second);
		update(1,1,idx,ST[nxt.first],EN[nxt.first],2*nxt.second);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for(int i=0;i<M;i++){
		adj[A[i]].push_back({B[i],T[i]});
		adj[B[i]].push_back({A[i],T[i]});
	}
	vector<int> v;
	int ans=0;
	for(int i=0;i<N;i++){
		//for every tree, find root s.t the distance between the root and the furthest leaf is minimum
		if(visited[i])continue;
		idx=0;
		dfs(i,-1,0);
		build(1,1,idx);
		furthest=1e9;
		diameter=0;
		dfsR(i,-1);
		ans=max(ans,diameter);
		v.push_back(furthest);
	}
	sort(v.begin(),v.end());
	reverse(v.begin(),v.end());
	if(v.size()==2)ans=max(ans,v[0]+v[1]+L);
	else if(v.size()>=3){
		int ret=1e9;
		ret=min(ret,max(v[0]+v[1]+L,v[1]+v[2]+2*L));
		ret=min(ret,max(v[0]+v[1]+L,v[0]+v[2]+2*L));
		ret=min(ret,max(v[0]+v[1]+2*L,v[0]+v[2]+L));
		ans=max(ans,ret);
	}
	return ans;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23