Submission #812664

#	Time	Username	Problem	Language	Result	Execution time	Memory
812664		TimDee	Dreaming (IOI13_dreaming)	C++17	100 / 100	102 ms	27668 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;

struct DSU {
	vector<int> p,sz;
	DSU(int n) {
		forn(i,n) p.pb(i), sz.pb(1);
	}
	int get(int u) {
		return p[u]==u?u:get(p[u]);
	}
	void uni(int u, int v) {
		u=get(u),v=get(v);
		if (u==v) return;
		if (sz[u]<sz[v]) swap(u,v);
		sz[u]+=sz[v];
		p[v]=u;
	}
};

const int N=1e5+5;
vector<pi> adj[N];
bitset<N> vis;

int d[N], in[N];
void dfs(int u, int p) {
	in[u]=0;
	for(auto&e:adj[u]) {
		int v=e.f, w=e.s;
		if (v==p) continue;
		d[v]=d[u]+w;
		dfs(v,u);
		in[u]=max(in[u],in[v]+w);
	}
}

int ans=0;
pi find(int u, int p, int o) {
	ans=max(ans,o+in[u]);
	pi ret = {u, max(o,in[u])};
	vector<int> sf={0};
	reverse(all(adj[u]));
	for(auto&e:adj[u]) {
		int v=e.f, w=e.s;
		if (v==p) continue;
		sf.pb(max(sf.back(),in[v]+w));
	}
	reverse(all(adj[u]));
	int mx=0;
	for(auto&e:adj[u]) {
		int v=e.f, w=e.s;
		if (v==p) continue;
		sf.pop_back();
		auto x = find(v,u,max({o,mx,sf.back()})+w);
		if (x.s<ret.s) ret=x;
		mx=max(mx,in[v]+w);
	}
	return ret;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {

	forn(i,m) {
		int u=a[i],v=b[i],w=t[i];
		adj[u].pb({v,w});
		adj[v].pb({u,w});
	}

	DSU dsu(n);
	forn(i,n) for(auto&x:adj[i]) dsu.uni(i,x.f);
	vector<int> c;
	forn(i,n) {
		int u=dsu.get(i);
		if (vis[u]) continue;
		vis[u]=1;
		c.pb(u);
	}
	int k=c.size();
	vector<pi> z;
	forn(i,k) {
		d[c[i]]=0;
		dfs(c[i],-1);
		auto q=find(c[i],-1,0);
		swap(q.f,q.s);
		z.pb(q);
	}
	sort(all(z));
	for (int i=k-2; i>=0; --i) {
		int u=z[i].s, v=z[i+1].s;
		adj[u].pb({v,l});
		adj[v].pb({u,l});
		int x=z[i].f, y=z[i+1].f;
		assert(x<=y);
		z[i] = {max(x+l,y),z[i+1].s};
	}

	ans=0;
	d[0]=0;
	dfs(0,-1);
	find(0,-1,0);
	return ans;

}

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