Submission #812598

#	Time	Username	Problem	Language	Result	Execution time	Memory
812598		TimDee	Dreaming (IOI13_dreaming)	C++17	47 / 100	225 ms	26176 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});
	}

	forn(it,20) {

		DSU dsu(n);
		forn(i,n) for(auto&x:adj[i]) dsu.uni(i,x.f);
		vis.reset();
		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();
		for (int i=k&1; i<k; i+=2) {
			d[c[i]]=0;
			d[c[i+1]]=0;
			dfs(c[i],-1);
			dfs(c[i+1],-1);
			auto q1 = find(c[i],-1,0);
			auto q2 = find(c[i+1],-1,0);
			int u=q1.f, v=q2.f;
			adj[u].pb({v,l});
			adj[v].pb({u,l});
		}

	}

	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: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23