Submission #304968

#	Time	Username	Problem	Language	Result	Execution time	Memory
304968		vipghn2003	Race (IOI11_race)	C++14	0 / 100	21 ms	30080 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;

const int N=2e5+5;
int sz[N],up[N],dep[N],p[N][20],level[N];
vector<pii>adj[N];
bool vis[N];
map<int,int>mn[N];

void dfs(int x,int par=-1)
{
    for(int k=1;k<=18;k++) p[x][k]=p[p[x][k-1]][k-1];
    for(auto&u:adj[x])
    {
        if(u.fi==par) continue;
        p[u.fi][0]=x;
        dep[u.fi]=dep[x]+u.se;
        level[u.fi]=level[x]+1;
        dfs(u.fi,x);
    }
}

int lca(int x,int y)
{
    if(level[x]>level[y]) swap(x,y);
    int diff=level[y]-level[x];
    for(int k=18;k>=0;k--) if(diff>>k&1) y=p[y][k];
    if (x==y) return x;
    for(int k=18;k>=0;k--)
    {
        if (p[x][k]!=p[y][k])
        {
            x=p[x][k];
            y=p[y][k];
        }
    }
    return p[x][0];
}

int dist1(int u,int v)
{
    return dep[u]+dep[v]-2*dep[lca(u,v)];
}

int dist2(int u,int v)
{
    return level[u]+level[v]-2*level[lca(u,v)];
}

void findsz(int u,int p=-1)
{
	sz[u]=1;
	for(auto&v:adj[u])
    {
		if (v.fi!=p&&!vis[v.fi])
		{
			findsz(v.fi,u);
			sz[u]+=sz[v.fi];
		}
	}
}

int find_cen(int u,int p,int m)
{
	for(auto&v:adj[u])
	{
		if(v.fi!=p&&!vis[v.fi])
        {
			if (sz[v.fi]>m/2) return find_cen(v.fi,u,m);
		}
	}
	return u;
}

void centroid(int root=0,int p=-1)
{
    findsz(root,root);
	int k=find_cen(root,root,sz[root]);
	up[k]=p;
	vis[k]=true;
	for(auto&u:adj[k]) if(!vis[u.fi])centroid(u.fi,k);
}

int best_path(int n,int k,int h[][2],int l[])
{
    for(int i=0;i<n-1;i++)
    {
        adj[h[i][0]].push_back(mp(h[i][1],l[i]));
        adj[h[i][1]].push_back(mp(h[i][0],l[i]));
    }
    memset(p,-1,sizeof p);
    dfs(0);
    centroid();

    for(int i=0;i<n;i++)
    {
        int cur=i;
        while(cur!=-1)
        {
            int d=dist1(i,cur);
            if(!mn[cur].count(d)) mn[cur][d]=dist2(i,cur);
            else mn[cur][d]=min(mn[cur][d],dist2(i,cur));
            cur=up[cur];
        }
    }
    int res=1e9;
    for(int i=0;i<n;i++)
    {
        int cur=i;
        while(cur!=-1)
        {
            int d=dist1(i,cur);
            if(mn[cur].count(k-d)) res=min(res,dist2(i,cur)+mn[cur][k-d]);
            cur=up[cur];
        }
    }
    if(res==1e9) res=-1;
    return res;
}
/*
int main()
{
    int n,k;
    cin>>n>>k;
    int h[n][2],l[n];
    for(int i=0;i<n-1;i++) cin>>h[i][0]>>h[i][1];
    for(int i=0;i<n-1;i++) cin>>l[i];
    cout<<best_path(n,k,h,l);
}
4 3
0 1
1 2
1 3
1 2 4
*/

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