oj.uz

Submission #1071830

# Submission time Handle Problem Language Result Execution time Memory
1071830 2024-08-23T11:40:14 Z LIF Race (IOI11_race) C++14
21 / 100
 3000 ms 107092 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 78684 KB Output is correct
2 Correct 30 ms 78724 KB Output is correct
3 Correct 38 ms 78672 KB Output is correct
4 Correct 30 ms 78680 KB Output is correct
5 Correct 27 ms 80244 KB Output is correct
6 Correct 31 ms 83028 KB Output is correct
7 Correct 19 ms 83032 KB Output is correct
8 Correct 16 ms 78680 KB Output is correct
9 Correct 27 ms 78724 KB Output is correct
10 Correct 31 ms 78756 KB Output is correct
11 Correct 26 ms 78816 KB Output is correct
12 Correct 42 ms 78684 KB Output is correct
13 Correct 26 ms 78680 KB Output is correct
14 Correct 45 ms 78672 KB Output is correct
15 Correct 20 ms 83032 KB Output is correct
16 Correct 24 ms 83028 KB Output is correct
17 Correct 23 ms 83036 KB Output is correct
18 Correct 24 ms 83104 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 78684 KB Output is correct
2 Correct 30 ms 78724 KB Output is correct
3 Correct 38 ms 78672 KB Output is correct
4 Correct 30 ms 78680 KB Output is correct
5 Correct 27 ms 80244 KB Output is correct
6 Correct 31 ms 83028 KB Output is correct
7 Correct 19 ms 83032 KB Output is correct
8 Correct 16 ms 78680 KB Output is correct
9 Correct 27 ms 78724 KB Output is correct
10 Correct 31 ms 78756 KB Output is correct
11 Correct 26 ms 78816 KB Output is correct
12 Correct 42 ms 78684 KB Output is correct
13 Correct 26 ms 78680 KB Output is correct
14 Correct 45 ms 78672 KB Output is correct
15 Correct 20 ms 83032 KB Output is correct
16 Correct 24 ms 83028 KB Output is correct
17 Correct 23 ms 83036 KB Output is correct
18 Correct 24 ms 83104 KB Output is correct
19 Correct 25 ms 83036 KB Output is correct
20 Correct 40 ms 83024 KB Output is correct
21 Correct 31 ms 83028 KB Output is correct
22 Correct 32 ms 83040 KB Output is correct
23 Correct 26 ms 83032 KB Output is correct
24 Correct 28 ms 82956 KB Output is correct
25 Correct 25 ms 83036 KB Output is correct
26 Correct 28 ms 83036 KB Output is correct
27 Correct 27 ms 83036 KB Output is correct
28 Correct 30 ms 78788 KB Output is correct
29 Correct 27 ms 78680 KB Output is correct
30 Correct 29 ms 78684 KB Output is correct
31 Correct 39 ms 78676 KB Output is correct
32 Correct 22 ms 83032 KB Output is correct
33 Correct 28 ms 83036 KB Output is correct
34 Correct 28 ms 82972 KB Output is correct
35 Correct 36 ms 83036 KB Output is correct
36 Correct 27 ms 83024 KB Output is correct
37 Correct 29 ms 83036 KB Output is correct
38 Correct 29 ms 83064 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 78684 KB Output is correct
2 Correct 30 ms 78724 KB Output is correct
3 Correct 38 ms 78672 KB Output is correct
4 Correct 30 ms 78680 KB Output is correct
5 Correct 27 ms 80244 KB Output is correct
6 Correct 31 ms 83028 KB Output is correct
7 Correct 19 ms 83032 KB Output is correct
8 Correct 16 ms 78680 KB Output is correct
9 Correct 27 ms 78724 KB Output is correct
10 Correct 31 ms 78756 KB Output is correct
11 Correct 26 ms 78816 KB Output is correct
12 Correct 42 ms 78684 KB Output is correct
13 Correct 26 ms 78680 KB Output is correct
14 Correct 45 ms 78672 KB Output is correct
15 Correct 20 ms 83032 KB Output is correct
16 Correct 24 ms 83028 KB Output is correct
17 Correct 23 ms 83036 KB Output is correct
18 Correct 24 ms 83104 KB Output is correct
19 Correct 113 ms 94036 KB Output is correct
20 Correct 124 ms 94032 KB Output is correct
21 Correct 145 ms 94060 KB Output is correct
22 Correct 117 ms 93916 KB Output is correct
23 Correct 92 ms 93852 KB Output is correct
24 Correct 54 ms 93524 KB Output is correct
25 Correct 116 ms 101212 KB Output is correct
26 Correct 78 ms 101712 KB Output is correct
27 Execution timed out 3070 ms 107092 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 78684 KB Output is correct
2 Correct 30 ms 78724 KB Output is correct
3 Correct 38 ms 78672 KB Output is correct
4 Correct 30 ms 78680 KB Output is correct
5 Correct 27 ms 80244 KB Output is correct
6 Correct 31 ms 83028 KB Output is correct
7 Correct 19 ms 83032 KB Output is correct
8 Correct 16 ms 78680 KB Output is correct
9 Correct 27 ms 78724 KB Output is correct
10 Correct 31 ms 78756 KB Output is correct
11 Correct 26 ms 78816 KB Output is correct
12 Correct 42 ms 78684 KB Output is correct
13 Correct 26 ms 78680 KB Output is correct
14 Correct 45 ms 78672 KB Output is correct
15 Correct 20 ms 83032 KB Output is correct
16 Correct 24 ms 83028 KB Output is correct
17 Correct 23 ms 83036 KB Output is correct
18 Correct 24 ms 83104 KB Output is correct
19 Correct 25 ms 83036 KB Output is correct
20 Correct 40 ms 83024 KB Output is correct
21 Correct 31 ms 83028 KB Output is correct
22 Correct 32 ms 83040 KB Output is correct
23 Correct 26 ms 83032 KB Output is correct
24 Correct 28 ms 82956 KB Output is correct
25 Correct 25 ms 83036 KB Output is correct
26 Correct 28 ms 83036 KB Output is correct
27 Correct 27 ms 83036 KB Output is correct
28 Correct 30 ms 78788 KB Output is correct
29 Correct 27 ms 78680 KB Output is correct
30 Correct 29 ms 78684 KB Output is correct
31 Correct 39 ms 78676 KB Output is correct
32 Correct 22 ms 83032 KB Output is correct
33 Correct 28 ms 83036 KB Output is correct
34 Correct 28 ms 82972 KB Output is correct
35 Correct 36 ms 83036 KB Output is correct
36 Correct 27 ms 83024 KB Output is correct
37 Correct 29 ms 83036 KB Output is correct
38 Correct 29 ms 83064 KB Output is correct
39 Correct 113 ms 94036 KB Output is correct
40 Correct 124 ms 94032 KB Output is correct
41 Correct 145 ms 94060 KB Output is correct
42 Correct 117 ms 93916 KB Output is correct
43 Correct 92 ms 93852 KB Output is correct
44 Correct 54 ms 93524 KB Output is correct
45 Correct 116 ms 101212 KB Output is correct
46 Correct 78 ms 101712 KB Output is correct
47 Execution timed out 3070 ms 107092 KB Time limit exceeded
48 Halted 0 ms 0 KB -