Submission #1071830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071830		LIF	Race (IOI11_race)	C++14	21 / 100	3070 ms	107092 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
long long int rt,sum,n,m,head[500005],query[500005],maxn[500005],siz[500005],judge[100000015],rem[500005],dis[500005],q[500005],edge_num[500005],dis2[500005]; // rt為當前的根，sum為當前子樹大小
long long int mine[10000010];
//rem : 存儲dis的值
int cnt = 0;
long long int T;
bool vis[500005],test[500005];
long long int ans = 1e9;
struct e
{
    int to;
    int val;
    int next;
}edge[500005];
void add(int x,int y,int val)
{
    cnt++;
    edge[cnt].to = y;
    edge[cnt].next = head[x];
    edge[cnt].val = val;
    head[x] = cnt;
}
void getrt(int now,int fa)
{
    siz[now] = 1;maxn[now] = 0;
    for(int i=head[now];i!=0;i=edge[i].next)
    {
        int to = edge[i].to;
        if(to == fa || vis[to] == true)continue;
        getrt(to,now);
        siz[now] += siz[to];
        maxn[now] = max(maxn[now],siz[to]);
    }
    maxn[now] = max(maxn[now],sum - siz[now]);
    if(maxn[now] < maxn[rt])rt = now;
    return;
}
void getdis(int now,int fa)
{
    rem[0]++;
    rem[rem[0]] = dis[now];
    edge_num[rem[0]] = dis2[now];
    for(int i=head[now];i!=0;i=edge[i].next)
    {
        int to = edge[i].to;
        if(to == fa || vis[to] == true)continue;
        dis[to] = dis[now] + edge[i].val;
        dis2[to] = dis2[now] + 1;
        getdis(to,now);
    }
}
void calc(int now)
{
    mine[0] = 0;int num = 0;
    for(int i=head[now];i!=0;i=edge[i].next)
    {
        int to = edge[i].to;
        if(vis[to] == true)continue;
        rem[0] = 0;
        dis[to] = edge[i].val;
        dis2[to] = 1;
        getdis(to,now);
        //cout<<now<<" "<<to<<endl;
        
        for(int j=rem[0];j>=1;j--)
        {
            long long int num1 = rem[j];
            long long int num2 = edge_num[j];
            if(T - num1 >= 0)
            {
                ans = min(ans,mine[T-num1]+num2);
            }
        }
        for(int j=rem[0];j>=1;j--)
        {
            num++;
            q[num] = rem[j];
            if(rem[j] <= T)mine[rem[j]] = min(mine[rem[j]],edge_num[j]);
        }
    }
    for(int i=1;i<=num;i++)
    {
        if(q[i] <= T)mine[q[i]] = 1e9; //清空，注意，== T是不需要清空的，因為mine[T]就是目標，若清空了則只會留下最後一棵子樹!

    }
}

void solve(int now)
{
    vis[now] = true;mine[0] = 0;
    calc(now);
    for(int i=head[now];i!=0;i=edge[i].next)
    {
        int to = edge[i].to;
        if(vis[to] == true)continue;
        sum = siz[to];
        maxn[rt = 0] = 1e9;
        getrt(to,0);
        solve(rt);
    }
    return;
}
int best_path(int N, int K, int H[][2], int L[])
{
  n = N;
  T = K;
  for(int i=1;i<=1e7;i++)mine[i] = 1e9;
  for(int i=0;i<=n-2;i++)
  {
    int u,v,w;
    u = H[i][0];
    v = H[i][1];
    w = L[i];
    add(u,v,w);
    add(v,u,w);
  }
  maxn[rt] = sum = n;
    getrt(1,0);
    solve(rt);
  if(ans == 1e9)return -1;
  else return ans;
}

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