oj.uz

Submission #812638

# Submission time Handle Problem Language Result Execution time Memory
812638 2023-08-07T09:44:47 Z I_Love_EliskaM_ Dreaming (IOI13_dreaming) C++17
0 / 100
 419 ms 22136 KB 
#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();
		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));
		reverse(all(z));
		vector<pi> z2;
		int r=0;
		for (int i=0; i<k; ++i) {
			r=max(r,i+1);
			while (r<k && z[k].f+l>z[i].f) ++k;
			if (r>=k) {
				z2.pb(z[i]); continue;
			}
			int u=z[i].s, v=z[r].s;
			adj[u].pb({v,l});
			adj[v].pb({u,l});
			++r;
		}
		k=z2.size();
		forn(i,k/2) {
			int u=z2[i].s, v=z2[(k/2)+i].s;
			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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 22136 KB Output is correct
2 Correct 354 ms 17732 KB Output is correct
3 Correct 216 ms 15340 KB Output is correct
4 Correct 42 ms 5332 KB Output is correct
5 Correct 35 ms 3912 KB Output is correct
6 Correct 85 ms 5980 KB Output is correct
7 Runtime error 4 ms 5332 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Runtime error 4 ms 5204 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 22136 KB Output is correct
2 Correct 354 ms 17732 KB Output is correct
3 Correct 216 ms 15340 KB Output is correct
4 Correct 42 ms 5332 KB Output is correct
5 Correct 35 ms 3912 KB Output is correct
6 Correct 85 ms 5980 KB Output is correct
7 Runtime error 4 ms 5332 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 15540 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Runtime error 4 ms 5204 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 22136 KB Output is correct
2 Correct 354 ms 17732 KB Output is correct
3 Correct 216 ms 15340 KB Output is correct
4 Correct 42 ms 5332 KB Output is correct
5 Correct 35 ms 3912 KB Output is correct
6 Correct 85 ms 5980 KB Output is correct
7 Runtime error 4 ms 5332 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -