oj.uz

Submission #426424

# Submission time Handle Problem Language Result Execution time Memory
426424 2021-06-14T02:44:43 Z hibye1217 Dreaming (IOI13_dreaming) C++17
0 / 100
 41 ms 9540 KB 
#ifndef NOTSUBMIT
#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
#endif // NOTSUBMIT

// Only Subtask 2
// Will do Subtask 1 later

int n, m;

typedef long long ll;
typedef pair<ll, ll> pl2;
#define fr first
#define sc second
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;
}

bool chk[100020];
pl2 dfs(int st){
	stack<pl2> stk;
	memset(chk, 0, sizeof(chk));
	stk.push({st, 0});
	pl2 res = {st, 0};
	while (!stk.empty()){
		int now = stk.top().fr; ll dst = stk.top().sc;
		if (res.sc < dst){ res = {now, dst}; }
		for (pl2 p : adj[now]){
			int nxt = p.fr; ll d = p.sc;
			if (chk[nxt]){ continue; }
			chk[nxt] = 1;
			stk.push({ nxt, dst+d });
		}
	}
	return res;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N; m = M;
	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]);
	}
	if (m == n-2){
		if (n <= 100){ // Subtask 2
			ll ans = 1e12;
			for (int i = 0; i < N; i++){
				for (int j = 0; j < N; j++){
					if (fnd(i) == fnd(j)){ continue; }
					adj[i].push_back({j, L});
					adj[j].push_back({i, L});
					ans = min( ans, dfs( dfs(0).fr ).sc );
				}
			}
			return ans;
		}
		else{ // Subtask 1, Not Implemented Yet

		}
	}
	return -1;
}

Subtask #1
0 / 14.0

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

Subtask #4
0 / 18.0

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