Submission #171046

#	Time	Username	Problem	Language	Result	Execution time	Memory
171046		dennisstar	Dreaming (IOI13_dreaming)	C++11	100 / 100	245 ms	31768 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;

int N, M, L;
int *A, *B, *T;
vim V[100010], C[100010];
vector<pii> D1[100010];
vim D2[100010];
int chk[100010];
vim ar;
int mx;

int dfs1(int now, int par, int dep) {
	chk[now]=1;
	for (int i=0; i<V[now].size(); i++) {
		if (chk[V[now][i]]) continue;
		D1[now].push_back({dfs1(V[now][i], now, dep+C[now][i])-dep, V[now][i]});
	}
	int ret=dep;
	for (int i=0; i<D1[now].size(); i++) ret=max(ret, D1[now][i].fi+dep);
	return ret;
}

int dfs2(int now, int dep) {
	chk[now]=1;
	if (!D1[now].size()) return dep;
	mx=max(mx, dep+D1[now][0].fi);
	if (D1[now].size()>1) mx=max(mx, D1[now][0].fi+D1[now][1].fi);
	int ret=max(dep, D1[now][0].fi);
	for (int i=0; i<V[now].size(); i++) {
		if (chk[V[now][i]]) continue;
		ret=min(ret, dfs2(V[now][i], max(dep, (D1[now][0].se==V[now][i]?(D1[now].size()>1?D1[now][1].fi:0):D1[now][0].fi))+C[now][i]));
	}
	return ret;
}

int travelTime(int N_, int M_, int L_, int A_[], int B_[], int T_[]) {
	N=N_; M=M_; L=L_; A=A_; B=B_; T=T_;
	for (int i=0; i<M; i++) {
		V[A[i]+1].push_back(B[i]+1);
		V[B[i]+1].push_back(A[i]+1);
		C[A[i]+1].push_back(T[i]);
		C[B[i]+1].push_back(T[i]);
	}
	for (int i=1; i<=N; i++) if (!chk[i]) {dfs1(i, 0, 0);}
	for (int i=1; i<=N; i++) sort(all(D1[i]), [](pii x1, pii x2){return x1.fi>x2.fi;});
	for (int i=1; i<=N; i++) chk[i]=0;
	for (int i=1; i<=N; i++) if (!chk[i]) {ar.push_back(dfs2(i, 0));}
	sort(all(ar), [](int x1, int x2){return x1>x2;});
	if (ar.size()==1) return mx;
	mx=max(mx, ar[0]+ar[1]+L);
	if (ar.size()>2) mx=max(mx, ar[1]+ar[2]+2*L);
	return mx;
}

Compilation message (stderr)

dreaming.cpp: In function 'int dfs1(int, int, int)':
dreaming.cpp:26:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<V[now].size(); i++) {
                ~^~~~~~~~~~~~~~
dreaming.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<D1[now].size(); i++) ret=max(ret, D1[now][i].fi+dep);
                ~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int dfs2(int, int)':
dreaming.cpp:41:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<V[now].size(); i++) {
                ~^~~~~~~~~~~~~~

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