oj.uz

답안 #426429

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
426429 2021-06-14T02:53:31 Z hibye1217 꿈 (IOI13_dreaming) C++17
0 / 100
 42 ms 8260 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; stk.pop();
		//cout << "DFS " << now << ' ' << dst << endl;
		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[]) {
	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]);
	}
	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; }
					//cout << "PAIR " << i << ' ' << j << endl;
					adj[i].push_back({j, L});
					adj[j].push_back({i, L});
					ans = min( ans, dfs( dfs(0).fr ).sc );
					adj[i].pop_back();
					adj[j].pop_back();
				}
			}
			return ans;
		}
		else{ // Subtask 1, Not Implemented Yet
			return -1;
		}
	}
	return -1;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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