oj.uz

Submission #311950

# Submission time Handle Problem Language Result Execution time Memory
311950 2020-10-12T03:48:00 Z T0p_ Factories (JOI14_factories) C++14
15 / 100
 8000 ms 241408 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

#define N 500500
#define pb push_back

struct GRAPH
{
	int node;
	long long weight;
};

int sz[N], pa[N], lv[N], jmp_node[20][N];
long long dis[N], jmp_dis[20][N], dp[20][N];
bool visit[N];
vector<GRAPH> g[N];
queue<int> bt;

int get_sz(int u, int p)
{
	sz[u] = 1;
	for(auto x : g[u])
	{
		if(visit[x.node] || x.node == p) continue ;
		sz[u] += get_sz(x.node, u);
	}
	return sz[u];
}

int get_centroid(int u, int p, int n)
{
	bool ch = (n - sz[u] <= n/2) ? true : false;
	int nu = 0, nf = 0;
	for(auto x : g[u])
	{
		if(visit[x.node] || x.node == p) continue ;
		if(sz[x.node] > n/2)
		{
			ch = false;
			if(sz[x.node] > nf)
			{
				nf = sz[x.node];
				nu = x.node;
			}
		}
	}
	return (ch) ? u : get_centroid(nu, u, n);
}

int build(int u, int p)
{
	int c = get_centroid(u, p, get_sz(u, p));
	visit[c] = true;
	for(auto x : g[c])
	{
		if(visit[x.node]) continue ;
		pa[build(x.node, c)] = c;
	}
	return c;
}

void dfs(int u, int l)
{
	lv[u] = l;
	for(auto x : g[u])
	{
		if(lv[x.node]) continue ;
		jmp_node[0][x.node] = u;
		jmp_dis[0][x.node] = x.weight;
		dfs(x.node, l+1);
	}
}

long long get_dis(int u, int v)
{
	long long ret = 0;
	if(lv[u] < lv[v]) swap(u, v);
	for(int i=19 ; i>=0 ; i--)
		if(lv[jmp_node[i][u]] >= lv[v])
		{
			ret += jmp_dis[i][u];
			u = jmp_node[i][u];
		}
	if(u == v) return ret;
	for(int i=19 ; i>=0 ; i--)
		if(jmp_node[i][u] != jmp_node[i][v])
		{
			ret += jmp_dis[i][u] + jmp_dis[i][v];
			u = jmp_node[i][u], v = jmp_node[i][v];
		}
	return ret + jmp_dis[0][u] + jmp_dis[0][v];
}

void Init(int n, int u[], int v[], int w[])
{
	for(int i=0 ; i<n-1 ; i++)
	{
		g[u[i]+1].pb({v[i]+1, w[i]});
		g[v[i]+1].pb({u[i]+1, w[i]});
	}
	dfs(1, 1);
	build(1, 0);
	for(int i=1 ; i<=n ; i++)
	{
		visit[i] = false;
		dis[i] = 1e15;
	}
	for(int i=1 ; i<20 ; i++)
		for(int j=1 ; j<=n ; j++)
		{
			jmp_node[i][j] = jmp_node[i-1][jmp_node[i-1][j]];
			jmp_dis[i][j] = jmp_dis[i-1][j] + jmp_dis[i-1][jmp_node[i-1][j]];
		}
	for(int i=1 ; i<=n ; i++)
	{
		int now = i;
		for(int j=0 ; true ; j++, now = pa[now])
		{
			assert(j <= 20);
			if(!now) break ;
			dp[j][i] = get_dis(i, now);
		}
	}
}

long long Query(int s, int x[], int t, int y[])
{
	long long ans = 1e15;
	for(int i=0 ; i<s ; i++)
	{
		int now = x[i]+1;
		for(int j=0 ; true ; j++, now = pa[now])
		{
			assert(j <= 20);
			if(!now) break ;
			if(!visit[now])
			{
				visit[now] = true;
				bt.push(now);
			}
			dis[now] = min(dis[now], dp[j][x[i]+1]);
		}
	}
	for(int i=0 ; i<t ; i++)
	{
		int now = y[i]+1;
		for(int j=0 ; true ; j++, now = pa[now])
		{
			assert(j <= 20);
			if(!now) break ;
			ans = min(ans, dis[now] + dp[j][y[i]+1]);
		}
	}
	while(!bt.empty())
	{
		visit[bt.front()] = false;
		dis[bt.front()] = 1e15;
		bt.pop();
	}
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13176 KB Output is correct
2 Correct 344 ms 23032 KB Output is correct
3 Correct 373 ms 23032 KB Output is correct
4 Correct 367 ms 32248 KB Output is correct
5 Correct 392 ms 32376 KB Output is correct
6 Correct 278 ms 31644 KB Output is correct
7 Correct 376 ms 32248 KB Output is correct
8 Correct 374 ms 32248 KB Output is correct
9 Correct 393 ms 32376 KB Output is correct
10 Correct 274 ms 31612 KB Output is correct
11 Correct 378 ms 32124 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12800 KB Output is correct
2 Correct 3516 ms 238140 KB Output is correct
3 Execution timed out 8055 ms 241408 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13176 KB Output is correct
2 Correct 344 ms 23032 KB Output is correct
3 Correct 373 ms 23032 KB Output is correct
4 Correct 367 ms 32248 KB Output is correct
5 Correct 392 ms 32376 KB Output is correct
6 Correct 278 ms 31644 KB Output is correct
7 Correct 376 ms 32248 KB Output is correct
8 Correct 374 ms 32248 KB Output is correct
9 Correct 393 ms 32376 KB Output is correct
10 Correct 274 ms 31612 KB Output is correct
11 Correct 378 ms 32124 KB Output is correct
12 Correct 10 ms 12800 KB Output is correct
13 Correct 3516 ms 238140 KB Output is correct
14 Execution timed out 8055 ms 241408 KB Time limit exceeded
15 Halted 0 ms 0 KB -