Submission #1087138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087138		quangminh412	Race (IOI11_race)	C++14	9 / 100	1592 ms	23984 KiB

race

#include <bits/stdc++.h>
using namespace std;

/*
  John Watson
  https://codeforces.com/profile/quangminh98

  Mua Code nhu mua Florentino !!
*/

#define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

const int maxn = 2e5 + 9;

vector<int> adj[maxn];
int sz[maxn], par[20][maxn], h[maxn], tp[maxn], id[maxn];
ll val[maxn], dist[maxn];
int n;
ll k;

//
ll st[4 * maxn];
void update(int head, int l, int r, int pos, ll val)
{
	if (l == r)
	{
		st[head] = val;
		return;
	}
	int mid = l + r >> 1;
	if (pos <= mid)
		update(2 * head, l, mid, pos, val);
	else
		update(2 * head + 1, mid + 1, r, pos, val);
		
	st[head] = st[2 * head] + st[2 * head + 1];
}
void update(int pos, ll val) { update(1, 1, n, pos, val); }

ll query(int head, int l, int r, int u, int v) 
{
	if (l > v || r < u) return 0ll;
	if (u <= l && r <= v) return st[head];
	
	int mid = l + r >> 1;
	return query(2 * head, l, mid, u, v) + query(2 * head + 1, mid + 1, r, u, v);
}
ll query(int u, int v) { return query(1, 1, n, u, v); } 
//

void DFS(int u, int p = -1)
{
	sz[u] = 1;
	
	for (int v : adj[u])
	{
		if (v == p) continue;
		
		h[v] = h[u] + 1;
		par[0][v] = u;
		for (int i = 1; i < 20; i++)
			par[i][v] = par[i - 1][par[i - 1][v]];
			
		DFS(v, u);
		
		sz[u] += sz[v];
	}
}

int LCA(int u, int v)
{
	if (h[u] < h[v]) swap(u, v);
	int k = h[u] - h[v];
	
	for (int i = 0; i < 20; i++)
		if (k >> i & 1)
			u = par[i][u];
			
	if (u == v) return u;
	
	for (int i = 19; i >= 0; i--)
		if (par[i][u] != par[i][v])
		{
			u = par[i][u];
			v = par[i][v];
		}
	
	return par[0][u];
}

int timeDFS = 0;
void HLD(int u, int p, int head)
{
	id[u] = ++timeDFS;
	tp[u] = head;
	update(id[u], val[u]);
	
	int nxt = -1;
	for (int v : adj[u])
	{
		if (v == p) continue;
		
		if (nxt == -1 || sz[nxt] < sz[v])
			nxt = v;
	}
	
	if (nxt != -1) HLD(nxt, u, head);
	
	for (int v : adj[u])
	{
		if (v == p || v == nxt) continue;
		
		HLD(v, u, v);
	}
}

ll queryPath(int u, int p)
{
	ll ans = 0;
	while (u != p)
		if (tp[u] == u)
		{
			ans += query(id[u], id[u]);
			u = par[0][u];
		} else
		if (h[tp[u]] > h[p])
		{
			ans += query(id[tp[u]], id[u]);
			u = par[0][tp[u]];
		} else
		{
			ans += query(id[p] + 1, id[u]);
			break;
		}
	return ans;
}

int best_path(int _n, int _k, int H[][2], int l[]) 
{
	n = _n;
	k = _k;
	for (int i = 0; i < n - 1; i++)
	{
		int u = H[i][0], v = H[i][1];
		u++; v++;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	DFS(1);
	for (int i = 0; i < n - 1; i++)
	{
		ll w = l[i];
		int u = H[i][0], v = H[i][1];
		u++; v++;
		val[h[u] > h[v] ? u : v] = w;
	}
	HLD(1, -1, 1);
	
	int ans = 1e9;
	
	for (int i = 1; i <= n; i++)
	  dist[i] = queryPath(i, 1);
	  
	 for (int u = 1; u <= n; u++)
	   for (int v = u + 1; v <= n; v++) 
	   {
	     if (h[u] > h[v]) swap(u, v);
	     int lca = LCA(u, v);
	     
	     ll distance;
	     if (lca == u)
	        distance = dist[v] - dist[u];
	     else
	        distance = dist[v] + dist[u] - 2 * dist[lca];
	        
	     if (distance == k) ans = min(ans, h[u] + h[v] - 2 * h[lca]);
	   }
	
	return (ans == 1e9 ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'void update(int, int, int, int, long long int)':
race.cpp:31:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |  int mid = l + r >> 1;
      |            ~~^~~
race.cpp: In function 'long long int query(int, int, int, int, int)':
race.cpp:46:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int mid = l + r >> 1;
      |            ~~^~~

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57