oj.uz

Submission #432181

# Submission time Handle Problem Language Result Execution time Memory
432181 2021-06-18T00:58:28 Z hibye1217 Dreaming (IOI13_dreaming) C++17
18 / 100
 69 ms 15548 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]; }
	if (ansv.size() == 2){ return ansv[0]+L+ansv[1]; }
	return max(ansv[0]+L+ansv[1], ansv[1]+L+L+ansv[2]);
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 15548 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 69 ms 15548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7880 KB Output is correct
2 Correct 36 ms 7944 KB Output is correct
3 Correct 40 ms 8284 KB Output is correct
4 Correct 45 ms 8372 KB Output is correct
5 Correct 37 ms 8296 KB Output is correct
6 Correct 40 ms 9288 KB Output is correct
7 Correct 35 ms 8648 KB Output is correct
8 Correct 35 ms 8256 KB Output is correct
9 Correct 44 ms 8232 KB Output is correct
10 Correct 50 ms 8432 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 17 ms 5992 KB Output is correct
13 Correct 14 ms 6068 KB Output is correct
14 Correct 15 ms 5996 KB Output is correct
15 Correct 14 ms 6044 KB Output is correct
16 Correct 13 ms 5996 KB Output is correct
17 Correct 14 ms 5996 KB Output is correct
18 Correct 14 ms 6176 KB Output is correct
19 Correct 15 ms 5996 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 3 ms 2764 KB Output is correct
23 Correct 14 ms 5984 KB Output is correct

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 69 ms 15548 KB Output isn't correct
2 Halted 0 ms 0 KB -