Submission #224544

#	Time	Username	Problem	Language	Result	Execution time	Memory
224544		amiratou	Dreaming (IOI13_dreaming)	C++14	100 / 100	106 ms	21244 KiB

dreaming

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int INF=(1e9+5);
vector<vector<pair<int,int> > > vec;
bitset<100001> vis;
int maxi[100001],h,d;
vector<int> f;
void dfs(int node){
	vis[node]=1;
	for(auto it:vec[node])
		if(!vis[it.fi]){
			dfs(it.fi);
			maxi[node]=max(maxi[node],maxi[it.fi]+it.se);
		}
}
void solve(int node,int p){
	h=min(h,maxi[node]);
	vector<int> g;
	for(auto it:vec[node])
		g.push_back(maxi[it.fi]+it.se);
	sort(g.begin(),g.end(),greater<int>());
	if(g.size()>1)d=max(d,g[0]+g[1]);
	else if(g.size()==1)d=max(d,g[0]);
	for(auto it:vec[node])
		if(it.fi!=p){
			int o=maxi[node],o2=maxi[it.fi];
			if(g.size()>1&&g[0]==(maxi[it.fi]+it.se))
				maxi[node]=g[1];
			else if(g.size()==1)maxi[node]=0;
			maxi[it.fi]=max(maxi[it.fi],maxi[node]+it.se);
			solve(it.fi,node);
			maxi[node]=o,maxi[it.fi]=o2;
		}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vec.resize(N);
    for (int i = 0; i < M; ++i)
    {
    	vec[A[i]].push_back({B[i],T[i]});
    	vec[B[i]].push_back({A[i],T[i]});
    }
    int ans=0;
    for (int i = 0; i < N; ++i)
    {
    	if(!vis[i]){
    		dfs(i);
    		h=INF,d=0,solve(i,i);
    		f.push_back(h),ans=max(d,ans);
    	}
    }
    sort(f.begin(),f.end(),greater<int>());
    if(f.size()>1)ans=max(ans,f[0]+f[1]+L);
    if(f.size()>2)ans=max(ans,f[1]+f[2]+2*L);
    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