Submission #367906

#	Time	Username	Problem	Language	Result	Execution time	Memory
367906		Pulgster	Dreaming (IOI13_dreaming)	C++17	100 / 100	173 ms	26476 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define imie(...) " [" << #__VA_ARGS__ " :" << (__VA_ARGS__) << "] "
#define ed <<endl
const int mxn = 1e5+5;
vector<vector<pair<int, int>>> adj(mxn);
struct unionFind{
	vector<int> par;
	vector<int> rnk;
	unionFind(int n){
		par.resize(n);
		rnk.resize(n);
		for(int i=0;i<n;i++){
			par[i]=i;
		}
	}
	int find(int p){
		if(par[p] != p){
			par[p]=find(par[p]);
		}
		return par[p];
	}
	void join(int u, int v){
		int uroot = find(u);
		int vroot = find(v);
		if(uroot == vroot){
			return;
		}
		if(rnk[vroot] > rnk[uroot]) swap(uroot, vroot);
		if(rnk[uroot] == rnk[vroot]) rnk[uroot]++;
		par[vroot] = uroot;
	}
};
vector<int> connected;
vector<int> mn(mxn, (1e9)+(1e8));
vector<vector<pair<int, int>>> ncosts(mxn);
int INF = 1e9+1;
int dfs1(int node, int par){
	connected.push_back(node);
	// cerr << imie(node) imie(curcost) ed;
	if(adj[node].size() == 1 && adj[node][0].first == par){
		mn[node]=0;
		return 0;
	}
	vector<pair<int, int>> costs;
	int mx=0;
	for(int i=0;i<adj[node].size();i++){
		int c = adj[node][i].second;
		int v=adj[node][i].first;
		if(v == par or v == node) continue;
		// cerr << imie(node) imie(v) ed;
		costs.push_back({dfs1(v, node)+c, v});
		mx=max(mx, costs.back().first);
	}
	mn[node] = min(mn[node], mx);
	sort(costs.begin(), costs.end());
	ncosts[node] = costs;
	return mx;
}
void dfs2(int node, int par, int ppar){
	mn[node] = max(mn[node], ppar);
	for(pair<int, int> i : adj[node]){
		int c=i.second;
		int v=i.first;
		if(v != par){
			if(ncosts[node].size() <= 1){
				dfs2(v, node, ppar+c);
			} else{
				int mx = ppar;
				if(ncosts[node].back().second == v){
					int sz=ncosts[node].size();
					mx = max(mx, ncosts[node][sz-2].first);
				} else{
					mx = max(mx, ncosts[node].back().first);
				}
				dfs2(v, node, mx+c);
			}
		}
	}
}
int ans = 0;
int dfs(int node, int par){
	vector<int> cur;
	int mx =0;
	for(pair<int, int> i : adj[node]){
		int v=i.first;
		int c=i.second;
		if(v == par) continue;
		cur.push_back(dfs(v, node)+c);
	}
	cur.push_back(0);
	cur.push_back(0);
	sort(cur.begin(), cur.end(),  greater<int>());
	mx=cur[0];
	int other = cur[1];
	ans = max(ans, mx + other);
	return mx;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
	unionFind uf(n);
	for(int i=0;i<m;i++){
		int u=a[i];
		int v=b[i];
		int c=t[i];
		// cerr << imie(u) imie(v) ed;
		adj[u].push_back({v, c});
		adj[v].push_back({u, c});

		uf.join(u, v);
	}
	vector<int> vis(n);
	vector<int> bests;
	int mx=-1;
	int center = -1;
	for(int i=0;i<n;i++){
		if(!vis[uf.find(i)]){
			//find a
			dfs1(uf.find(i), -1);
			dfs2(uf.find(i), -1, 0);
			int mns = INF;
			int no = -1;
			for(int i : connected){
				if(mn[i] < mns){
					no = i;
					mns = mn[i];
				}

			}
			if(mns > mx){
				center = no;
				mx = mns;
			}
			bests.push_back(no);
			connected.clear();
			vis[uf.find(i)] = 1;
		}
	}
	for(int i=0;i<bests.size();i++){
		if(bests[i] == center) continue;
		adj[center].push_back({bests[i], l});
		adj[bests[i]].push_back({center, l});
	}
	dfs(center, -1);

	return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'int dfs1(int, int)':
dreaming.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0;i<adj[node].size();i++){
      |              ~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:140:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |  for(int i=0;i<bests.size();i++){
      |              ~^~~~~~~~~~~~~

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