oj.uz

Submission #432177

# Submission time Handle Problem Language Result Execution time Memory
432177 2021-06-18T00:53:48 Z hibye1217 Dreaming (IOI13_dreaming) C++17
0 / 100
 60 ms 16800 KB 
#ifndef NOTSUBMIT
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#endif // NOTSUBMIT

typedef long long ll;
typedef pair<ll, ll> pl2;
#define fr first
#define sc second

#define all(v) v.begin(),v.end()

vector<pl2> adj[100020];
int par[100020];

inline int fnd(int a){
	if (par[a] == a){ return a; }
	return par[a] = fnd(par[a]);
}

inline void uni(int a, int b){
	int pa = fnd(a), pb = fnd(b);
	par[pa] = pb;
}

vector<int> upd;
pl2 res = {-1, -1};
void dfs1(int now, int pre, ll dis){
	upd.push_back(now);
	if (res.sc < dis){ res = {now, dis}; }
	for (pl2 p : adj[now]){
		int nxt = p.fr; ll dst = p.sc;
		if (nxt == pre){ continue; }
		dfs1(nxt, now, dis+dst);
	}
}

pl2 chk[100020];
void dfs2(int now, int pre, ll dis){
	chk[now] = {pre, dis};
	if (res.sc < dis){ res = {now, dis}; }
	for (pl2 p : adj[now]){
		int nxt = p.fr; ll dst = p.sc;
		if (nxt == pre){ continue; }
		dfs2(nxt, now, dis+dst);
	}
}

bool pac[100020];
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for (int i = 0; i < N; i++){ par[i] = i; }
	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] });
		uni(A[i], B[i]);
	}
	vector<ll> ansv;
	for (int i = 0; i < N; i++){
		int pai = fnd(i);
		if (pac[pai]){ continue; } pac[pai] = 1;
		res = {-1, -1}; dfs1(i, -1, 0); int mxp = res.fr;
		res = {-1, -1}; dfs2(mxp, -1, 0); int p = res.fr;
		vector<int> v;
		while (p != -1){ v.push_back(p); p = chk[p].fr; }
		int vl = v.size(); vector<ll> prf(vl);
		for (int i = 0; i < vl; i++){ prf[i] = chk[ v[i] ].sc; }
		ll ans = 1e15;
		for (int i = 0; i < vl; i++){
			ll res = max( prf[0]-prf[i], prf[i]-prf[vl-1] );
			ans = min(ans, res);
		}
		//cout << "ANSV " << i << ' ' << ans << endl;
		ansv.push_back(ans);
	}
	sort(all(ansv), [](ll a, ll b){ return a > b; });
	if (ansv.size() == 1){ return ansv[0]; }
	return ansv[0] + ansv[1] + L;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 16800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 16800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 8368 KB Output is correct
2 Incorrect 40 ms 8380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 16800 KB Output isn't correct
2 Halted 0 ms 0 KB -