Submission #383505

#	Time	Username	Problem	Language	Result	Execution time	Memory
383505		alishahali1382	Dreaming (IOI13_dreaming)	C++14	100 / 100	124 ms	16492 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

int n, m, k, u, v, x, y, t, a, b, ans;
int D[2][MAXN], mark[MAXN];
vector<pii> G[MAXN];
vector<int> vec, V;

void dfs(int node, int *dist){
	if (!mark[node]) V.pb(node);
	mark[node]++;
	for (pii p:G[node]) if (mark[p.first]<mark[node]){
		dist[p.first]=dist[node]+p.second;
		dfs(p.first, dist);
	}
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]){
	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 (!mark[i]){
		dfs(i, D[0]);
		int v=i;
		for (int u:V) if (D[0][u]>D[0][v]) v=u;
		dfs(v, D[1]);
		for (int u:V) if (D[1][u]>D[1][v]) v=u;
		D[0][v]=0;
		dfs(v, D[0]);
		int res=inf;
		for (int u:V){
			int val=max(D[0][u], D[1][u]);
			ans=max(ans, val);
			res=min(res, val);
		}
		vec.pb(res);
		V.clear();
	}
//	debugv(vec)
//	debug(ans)
	if (vec.size()==1) return ans;
	if (vec.size()==2) return max(ans, vec[0]+vec[1]+L);
	sort(all(vec));
	reverse(all(vec));
	vec.resize(3);
	int res=inf;
	do{
		int a=vec[0], x=vec[1], y=vec[2];
		res=min(res, max(2*L+x+y, L+x+a));
	} while(next_permutation(all(vec)));
	
	return max(ans, res);
}

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