제출 #970495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
970495		vjudge1	Race (IOI11_race)	C++17	21 / 100	2825 ms	262144 KiB

race

#include <bits/stdc++.h>
#define ll int
using namespace std;
#pragma GCC optimize("Ofast")
void YES()
{
    cout<<"YES\n";
}
void NO()
{
    cout<<"NO\n";
}
ll n;
ll answer = 2e9;
vector<ll> cnt;
vector<ll> par;
vector<ll> dist;
vector<ll> eddist;
vector<vector<ll>> st;
vector<ll> tin;
vector<ll> ins;
vector<ll> first;
vector<ll> inv;
vector<ll> po(200001,-1);
ll k;
vector<vector<map<ll,ll>>> oc;
ll T = 0;
void dfs2(ll v,vector<vector<vector<ll>>> & ed)
{
	tin[v] = ++T;
	inv[T] = v;
	first[v] = ins.size();
	ins.push_back(tin[v]);
	for (vector<ll> i : ed[v])
	{
		ll u = i[0];
		if (!tin[u])
		{
			eddist[u] = eddist[v]+1;
			dist[u] = dist[v]+i[1];
			dfs2(u,ed);
			ins.push_back(tin[v]);
		}
	}
}
void dfs(ll v,ll pr,vector<vector<vector<ll>>> & ed)
{
	cnt[v] = 1;
	for (vector<ll> i : ed[v])
	{
		ll u = i[0];
		if (par[u] != -1 || u == pr) continue;
		dfs(u,v,ed);
		cnt[v]+=cnt[u];
	}
}
ll cent(ll v,ll pr,ll s,vector<vector<vector<ll>>> & ed)
{
	for (vector<ll> i : ed[v])
	{
		ll u = i[0];
		if (u != pr && par[u] == -1 && cnt[u] > s/2)
		{
			return cent(u,v,s,ed);
		}
	}
	return v;
}
ll findlca(ll a,ll b)
{
	a = first[a],b = first[b];
	if (a > b) swap(a,b);
	ll k = po[b-a+1];
	return inv[min(st[k][a],st[k][b-(1 << k)+1])];
}
vector<ll> finddist(ll u,ll v)
{
	ll lca = findlca(u,v);
	return {dist[u]+dist[v]-2*dist[lca],eddist[u]+eddist[v]-2*eddist[lca]};
}
void paint(ll v,ll u)
{
	if (v == -2) return;
	vector<ll> d = finddist(u,v);
	if (oc[v][1].find(d[0]) != oc[v][1].end()) oc[v][1][d[0]] = min(oc[v][1][d[0]],d[1]);
	else oc[v][1][d[0]] = d[1];
	paint(par[v],u);
}
ll decomp(ll v,ll pr,vector<vector<vector<ll>>> & ed)
{
	dfs(v,-1,ed);
	ll s = cnt[v];
	ll c = cent(v,-1,s,ed);
	par[c] = pr;
	paint(c,c);
	oc[c][0][0]=0;
	// cout<<c+1<<" ";
	// cout<<c<<" "<<pr<<" "<<par[c]<<"\n";
 	for (vector<ll> i : ed[c])
	{
		ll u = i[0];
		if (par[u] == -1)
		{
			ll cen = decomp(u,c,ed);
			// cout<<cen<<" ";
			for (auto i : oc[c][1])
			{
				if (oc[c][0].find(k-i.first) == oc[c][0].end()) continue;
				answer = min(answer,i.second+oc[c][0][k-i.first]);
			}
			for (auto i : oc[c][1])
			{
				if (oc[c][0].find(i.first) == oc[c][0].end()) oc[c][0][i.first] = i.second;
				else oc[c][0][i.first] = min(oc[c][0][i.first],i.second);
			}
			oc[c][1].clear();
		}
	}
	// cout<<c<<"\n";
	// for (auto i : oc[c][0])
	// {
		// cout<<i.first<<" "<<i.second<<"\n";
	// }
	return c;
}
ll best_path(ll n,ll K,ll H[][2],ll L[])
{
	ll p = 0,d = 1;
	k = K;
	if (po[1] == -1)
	{
		for (ll e = 1;e<=200000;e++)
		{
			if (e == d*2)
			{
				p++;
				d*=2;
			}
			po[e] = p;
		}
	}
	eddist = vector<ll>(n,0);
	tin = vector<ll>(n,0);
	cnt = vector<ll>(n,0);
	par = vector<ll>(n,-1);
	first = vector<ll>(n,0);
	dist = vector<ll>(n,0);
	inv = vector<ll>(n+1,0);
	st = vector<vector<ll>>(2*n,vector<ll>(0));
	vector<vector<vector<ll>>> ed(n);
	oc = vector<vector<map<ll,ll>>>(n,vector<map<ll,ll>>(2));
	for (ll e = 0;e<n-1;e++)
	{
		ll u = H[e][0],v = H[e][1],we = L[e];
		ed[u].push_back({v,we});
		ed[v].push_back({u,we});
	}
	dfs2(0,ed);
	answer = 2e9;
	for (ll e = 0;e<(ll)ins.size();e++)
	{
		st[0].push_back(ins[e]);
	}
	for (ll k = 1;k<20;k++)
	{
		ll po = (1 << (k-1));
		for (ll e = 0;e<(ll)ins.size()-po*2+1;e++)
		{
			st[k].push_back(min(st[k-1][e],st[k-1][e+po]));
		}
	}
	decomp(0,-2,ed);
	if (answer == 2e9) return -1;
	return answer;
}
void ans()
{
	ll n,k;cin>>n>>k;
	ll H[n-1][2],L[n-1];
	for (ll e = 0;e<n-1;e++)
	{
		ll u,v;cin>>u>>v;
		H[e][0] = u;H[e][1] = v;
	}
	for (ll e = 0;e<n-1;e++)
	{
		ll we;cin>>we;
		L[e] = we;
	}
	cout<<best_path(n,k,H,L)<<"\n";
}
// int main()
// {
    // cin.tie(0);cout.tie(0);
    // ios_base::sync_with_stdio(0);
	// ll t = 1;
	// for (ll e = 1;e<=t;e++)
	// {
		// ans();
	// }
    // return 0;
// }

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int decomp(int, int, std::vector<std::vector<std::vector<int> > >&)':
race.cpp:104:7: warning: unused variable 'cen' [-Wunused-variable]
  104 |    ll cen = decomp(u,c,ed);
      |       ^~~

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