oj.uz

Submission #707888

# Submission time Handle Problem Language Result Execution time Memory
707888 2023-03-10T10:56:24 Z Pherokung Race (IOI11_race) C++14
100 / 100
 553 ms 37744 KB 
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
#define ll long long
#define pb push_back
#define X first
#define Y second
int n,ans=1e9,m,sz[200005],vis[200005],mn[1000005];
vector<pair<int,int> > v[200005];
void dfs_size(int u,int p)
{
    sz[u]=1;
    for(auto [node,w]:v[u])
    {
        if(vis[node]==0&&node!=p)
        {
            dfs_size(node,u);
            sz[u]+=sz[node];
        }
    }
}
int find_cen(int u,int p,int want)
{
    for(auto [node,w]:v[u])
    {
        if(node!=p&&vis[node]==0)
        {
            if(sz[node]>want)return find_cen(node,u,want);
        }
    }
    return u;
}
void compute(int u,int p,int type,int depth,int lv)
{
    //printf("%lld %lld %lld %lld %lld\n",u,p,type,depth,lv);
    if(depth>m)return;
    if(type==1)
    {
        ans=min(ans,lv+mn[m-depth]);
    }else if(type==0)
    {
        mn[depth]=min(mn[depth],lv);
    }else
    {
        mn[depth]=1e9,mn[m-depth]=1e9;
    }
    for(auto [node,w]:v[u])
    {
        if(node!=p&&vis[node]==0)compute(node,u,type,depth+w,lv+1);
    }
}
void centroid(int u)
{
    dfs_size(u,u);
    int cen=find_cen(u,u,sz[u]/2);
    //printf("cen=%d\n",cen);
    vis[cen]=1;
    for(auto [node,w]:v[cen])
    {
        if(vis[node]==0)compute(node,node,2,w,1);
    }
    mn[0]=0;
    for(auto [node,w]:v[cen])
    {
        if(vis[node]==0)
        {
            //printf("node=%lld\n",node);
            compute(node,node,1,w,1);
            /*for(int i=0;i<=m;i++)
            {
                printf("%lld ",mn[i]);
            }
            printf("\n");*/
            compute(node,node,0,w,1);
            /*for(int i=0;i<=m;i++)
            {
                printf("%lld ",mn[i]);
            }
            printf("\n");*/
        }
    }
    //printf("\n");
    for(auto [node,w]:v[cen])
    {
        if(vis[node]==0)
        {
            centroid(node);
        }
    }
    /*for(int i=1;i<=n;i++)
    {
        printf("%d ",vis[i]);
    }
    printf("\n");*/
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N,m=K;
    for(int i=0;i<n-1;i++)
    {
        v[H[i][0]+1].pb({H[i][1]+1,L[i]});
        v[H[i][1]+1].pb({H[i][0]+1,L[i]});
    }
    // for(int i=1;i<=n;i++)
    // {
    //     printf("i=%d\n",i);
    //     for(auto [node,w]:v[i])
    //     {
    //         printf("%d %d\n",node,w);
    //     }
    //     printf("\n");
    // }
    for(int i=1;i<=n;i++)vis[i]=0;
    for(int i=1;i<=1000000;i++)mn[i]=1e9;
    centroid(1);
    if(ans==1e9)return -1;
    return ans;
}

Compilation message

race.cpp: In function 'void dfs_size(int, int)':
race.cpp:14:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for(auto [node,w]:v[u])
      |              ^
race.cpp: In function 'int find_cen(int, int, int)':
race.cpp:25:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |     for(auto [node,w]:v[u])
      |              ^
race.cpp: In function 'void compute(int, int, int, int, int)':
race.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for(auto [node,w]:v[u])
      |              ^
race.cpp: In function 'void centroid(int)':
race.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto [node,w]:v[cen])
      |              ^
race.cpp:64:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |     for(auto [node,w]:v[cen])
      |              ^
race.cpp:84:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |     for(auto [node,w]:v[cen])
      |              ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 5 ms 8916 KB Output is correct
3 Correct 4 ms 8916 KB Output is correct
4 Correct 4 ms 8936 KB Output is correct
5 Correct 4 ms 8916 KB Output is correct
6 Correct 4 ms 8916 KB Output is correct
7 Correct 4 ms 8916 KB Output is correct
8 Correct 5 ms 8916 KB Output is correct
9 Correct 5 ms 8916 KB Output is correct
10 Correct 5 ms 8916 KB Output is correct
11 Correct 5 ms 8852 KB Output is correct
12 Correct 5 ms 8916 KB Output is correct
13 Correct 5 ms 8916 KB Output is correct
14 Correct 5 ms 8916 KB Output is correct
15 Correct 5 ms 8880 KB Output is correct
16 Correct 4 ms 8916 KB Output is correct
17 Correct 5 ms 8916 KB Output is correct
18 Correct 4 ms 8916 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 5 ms 8916 KB Output is correct
3 Correct 4 ms 8916 KB Output is correct
4 Correct 4 ms 8936 KB Output is correct
5 Correct 4 ms 8916 KB Output is correct
6 Correct 4 ms 8916 KB Output is correct
7 Correct 4 ms 8916 KB Output is correct
8 Correct 5 ms 8916 KB Output is correct
9 Correct 5 ms 8916 KB Output is correct
10 Correct 5 ms 8916 KB Output is correct
11 Correct 5 ms 8852 KB Output is correct
12 Correct 5 ms 8916 KB Output is correct
13 Correct 5 ms 8916 KB Output is correct
14 Correct 5 ms 8916 KB Output is correct
15 Correct 5 ms 8880 KB Output is correct
16 Correct 4 ms 8916 KB Output is correct
17 Correct 5 ms 8916 KB Output is correct
18 Correct 4 ms 8916 KB Output is correct
19 Correct 4 ms 8916 KB Output is correct
20 Correct 5 ms 8916 KB Output is correct
21 Correct 7 ms 8928 KB Output is correct
22 Correct 5 ms 8916 KB Output is correct
23 Correct 5 ms 8916 KB Output is correct
24 Correct 6 ms 8916 KB Output is correct
25 Correct 7 ms 8988 KB Output is correct
26 Correct 5 ms 8916 KB Output is correct
27 Correct 7 ms 8916 KB Output is correct
28 Correct 7 ms 8916 KB Output is correct
29 Correct 5 ms 8916 KB Output is correct
30 Correct 5 ms 8916 KB Output is correct
31 Correct 5 ms 8916 KB Output is correct
32 Correct 5 ms 8916 KB Output is correct
33 Correct 7 ms 8916 KB Output is correct
34 Correct 5 ms 8916 KB Output is correct
35 Correct 5 ms 8916 KB Output is correct
36 Correct 7 ms 8916 KB Output is correct
37 Correct 8 ms 8916 KB Output is correct
38 Correct 5 ms 8916 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 5 ms 8916 KB Output is correct
3 Correct 4 ms 8916 KB Output is correct
4 Correct 4 ms 8936 KB Output is correct
5 Correct 4 ms 8916 KB Output is correct
6 Correct 4 ms 8916 KB Output is correct
7 Correct 4 ms 8916 KB Output is correct
8 Correct 5 ms 8916 KB Output is correct
9 Correct 5 ms 8916 KB Output is correct
10 Correct 5 ms 8916 KB Output is correct
11 Correct 5 ms 8852 KB Output is correct
12 Correct 5 ms 8916 KB Output is correct
13 Correct 5 ms 8916 KB Output is correct
14 Correct 5 ms 8916 KB Output is correct
15 Correct 5 ms 8880 KB Output is correct
16 Correct 4 ms 8916 KB Output is correct
17 Correct 5 ms 8916 KB Output is correct
18 Correct 4 ms 8916 KB Output is correct
19 Correct 153 ms 14412 KB Output is correct
20 Correct 122 ms 14460 KB Output is correct
21 Correct 137 ms 14548 KB Output is correct
22 Correct 132 ms 14612 KB Output is correct
23 Correct 79 ms 14708 KB Output is correct
24 Correct 72 ms 14668 KB Output is correct
25 Correct 126 ms 18072 KB Output is correct
26 Correct 100 ms 23364 KB Output is correct
27 Correct 177 ms 23320 KB Output is correct
28 Correct 273 ms 37744 KB Output is correct
29 Correct 261 ms 36640 KB Output is correct
30 Correct 168 ms 23344 KB Output is correct
31 Correct 166 ms 23368 KB Output is correct
32 Correct 192 ms 23396 KB Output is correct
33 Correct 230 ms 22092 KB Output is correct
34 Correct 166 ms 23064 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 5 ms 8916 KB Output is correct
3 Correct 4 ms 8916 KB Output is correct
4 Correct 4 ms 8936 KB Output is correct
5 Correct 4 ms 8916 KB Output is correct
6 Correct 4 ms 8916 KB Output is correct
7 Correct 4 ms 8916 KB Output is correct
8 Correct 5 ms 8916 KB Output is correct
9 Correct 5 ms 8916 KB Output is correct
10 Correct 5 ms 8916 KB Output is correct
11 Correct 5 ms 8852 KB Output is correct
12 Correct 5 ms 8916 KB Output is correct
13 Correct 5 ms 8916 KB Output is correct
14 Correct 5 ms 8916 KB Output is correct
15 Correct 5 ms 8880 KB Output is correct
16 Correct 4 ms 8916 KB Output is correct
17 Correct 5 ms 8916 KB Output is correct
18 Correct 4 ms 8916 KB Output is correct
19 Correct 4 ms 8916 KB Output is correct
20 Correct 5 ms 8916 KB Output is correct
21 Correct 7 ms 8928 KB Output is correct
22 Correct 5 ms 8916 KB Output is correct
23 Correct 5 ms 8916 KB Output is correct
24 Correct 6 ms 8916 KB Output is correct
25 Correct 7 ms 8988 KB Output is correct
26 Correct 5 ms 8916 KB Output is correct
27 Correct 7 ms 8916 KB Output is correct
28 Correct 7 ms 8916 KB Output is correct
29 Correct 5 ms 8916 KB Output is correct
30 Correct 5 ms 8916 KB Output is correct
31 Correct 5 ms 8916 KB Output is correct
32 Correct 5 ms 8916 KB Output is correct
33 Correct 7 ms 8916 KB Output is correct
34 Correct 5 ms 8916 KB Output is correct
35 Correct 5 ms 8916 KB Output is correct
36 Correct 7 ms 8916 KB Output is correct
37 Correct 8 ms 8916 KB Output is correct
38 Correct 5 ms 8916 KB Output is correct
39 Correct 153 ms 14412 KB Output is correct
40 Correct 122 ms 14460 KB Output is correct
41 Correct 137 ms 14548 KB Output is correct
42 Correct 132 ms 14612 KB Output is correct
43 Correct 79 ms 14708 KB Output is correct
44 Correct 72 ms 14668 KB Output is correct
45 Correct 126 ms 18072 KB Output is correct
46 Correct 100 ms 23364 KB Output is correct
47 Correct 177 ms 23320 KB Output is correct
48 Correct 273 ms 37744 KB Output is correct
49 Correct 261 ms 36640 KB Output is correct
50 Correct 168 ms 23344 KB Output is correct
51 Correct 166 ms 23368 KB Output is correct
52 Correct 192 ms 23396 KB Output is correct
53 Correct 230 ms 22092 KB Output is correct
54 Correct 166 ms 23064 KB Output is correct
55 Correct 12 ms 9556 KB Output is correct
56 Correct 17 ms 9508 KB Output is correct
57 Correct 82 ms 16164 KB Output is correct
58 Correct 36 ms 15832 KB Output is correct
59 Correct 95 ms 23172 KB Output is correct
60 Correct 510 ms 36868 KB Output is correct
61 Correct 168 ms 23444 KB Output is correct
62 Correct 212 ms 23256 KB Output is correct
63 Correct 269 ms 23376 KB Output is correct
64 Correct 553 ms 23608 KB Output is correct
65 Correct 213 ms 24172 KB Output is correct
66 Correct 388 ms 34144 KB Output is correct
67 Correct 107 ms 23948 KB Output is correct
68 Correct 261 ms 24100 KB Output is correct
69 Correct 278 ms 24412 KB Output is correct
70 Correct 261 ms 23400 KB Output is correct