oj.uz

답안 #171043

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171043 2019-12-27T07:47:05 Z dennisstar 꿈 (IOI13_dreaming) C++11
0 / 100
 125 ms 24440 KB 
#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=1; i<D1[now].size(); i++) ret=max(ret, D1[now][i].fi+dep);
	return ret;
}

int dfs2(int now, int dep) {
	if (!D1[now].size()) return 0;
	mx=max(mx, dep+D1[now][0].fi);
	if (D1[now].size()>1) mx=max(mx, D1[now][0].fi+D1[now][1].fi);
	chk[now]=1;
	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;
	else return max(mx, ar[0]+ar[1]+L);
}

Compilation message

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=1; 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
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 125 ms 24440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 125 ms 24440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 125 ms 24440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 125 ms 24440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 125 ms 24440 KB Output isn't correct
2 Halted 0 ms 0 KB -