Submission #471379

#	Time	Username	Problem	Language	Result	Execution time	Memory
471379		PiejanVDC	꿈 (IOI13_dreaming)	C++17	47 / 100	244 ms	25812 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int,int>>>adj;
bool vis[100000];
map<int,int>mp,cnt;
vector<int>connect;

int dd(int node, int e) {
	vis[node]=true;
	int mx = 0, prev = node;
	for(auto z : adj[node]) {
		if(z.first == e) continue;
		auto ret = dd(z.first,node);
		if(mx <= ret+z.second)
			mx=ret+z.second,prev=z.first;
	}
	mp[node]=prev,cnt[node]=mx;
	return mx;
}

pair<int,int> d(int node, int e) {
	vis[node]=true;
	pair<int,int>mx = {0,node};
	for(auto z : adj[node]) {
		if(z.first == e) continue;
		auto ret = d(z.first,node);
		if(mx.first <= ret.first+z.second)
			mx.first=ret.first+z.second,mx.second=ret.second;
	}
	return mx;
}

void dia(int node) {
	int nd = d(node,-1).second;
	auto ans = dd(nd,-1);
	int curr = nd;
	while(cnt[mp[curr]] > ans/2) curr=mp[curr];
	if(cnt[curr] <= ans - cnt[mp[curr]]) {
		connect.push_back(curr);
	} else connect.push_back(mp[curr]);
	return;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
	adj.resize(n);
	for(int i = 0 ; i < m ; i++) {
		adj[a[i]].push_back(make_pair(b[i],t[i]));
		adj[b[i]].push_back(make_pair(a[i],t[i]));
	}
	for(int i = 0 ; i < n ; i++) {
		if(vis[i]) continue;
		dia(i);
	}
	for(int i = 0 ; i < (int)connect.size()-1 ; i++) {
		adj[connect[i]].push_back(make_pair(connect[i+1],l));
		adj[connect[i+1]].push_back(make_pair(connect[i],l));
	}
	int edge = d(0,-1).second;
	return d(edge,-1).first;
}

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