Submission #426432

#	Time	Username	Problem	Language	Result	Execution time	Memory
426432		hibye1217	Dreaming (IOI13_dreaming)	C++17	10 / 100	51 ms	8516 KiB

dreaming

#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}); chk[st] = 1;
	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 });
		}
	}
	//cout << endl;
	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 = i+1; 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
• Subtask 2: 10 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23