Submission #163371

#	Time	Username	Problem	Language	Result	Execution time	Memory
163371		kostia244	꿈 (IOI13_dreaming)	C++17	0 / 100	37 ms	2552 KiB

dreaming

#define _GLIBCXX_DEBUG
#include "dreaming.h"
#include<bits/stdc++.h>
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;
using pi = pair<ll, ll>;
using vpi = vector<pi>;
using vvpi = vector<vpi>;
int n;
vvpi g;
vi diams, comp;
bitset<5000> vis;
void dc(int v) {
	comp.pb(v);
	vis.set(v);
	for(auto i : g[v])
		if(!vis.test(i.first)) dc(i.first);
}
ll dfs(int v, int p) {
	ll x=0;
	for(auto i : g[v])
		if(i.first!=p) x = max(x, i.second+dfs(i.first, v));
	return x;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	return 18;
	n = N;
	g.resize(n);
	ll ans = 0;
	for(int f, t, c, i = 0; i < M; i++) {
		f = A[i], t = B[i], c = T[i];
		g[f].pb({t, c});
		g[t].pb({f, c});
//		cout <<f << " " <<t << "\n";
	}
	for(int i = 0; i < n; i++) {
		if(!vis[i]) {
			comp.clear();
			dc(i);
			ll d = LLONG_MAX;
			for(auto j : comp)
				d = min(d, dfs(j, j));
			diams.pb(d);
		}
	}
	sort(rall(diams));
	if(diams.size()==1)ans=diams[0];
	else ans = diams[0]+L+diams[1];
	if(diams.size()>2) ans = max(ans, diams[2]+L+L+diams[1]);
	return ans;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23