oj.uz

Submission #651827

# Submission time Handle Problem Language Result Execution time Memory
651827 2022-10-20T09:29:51 Z andrei_boaca Race (IOI11_race) C++14
100 / 100
 1353 ms 54120 KB 
#include <bits/stdc++.h>
#include "race.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
ll n,k,ans=1e9,dist[200005],niv[200005],nr[200005],par[200005];
vector<int> vals;
vector<vector<pii>> allvals;
int mini[1000005],m1[1000005],m2[1000005];
struct date
{
    ll a,b,cost;
} G[200005];
bool edgeuse[200005];
vector<int> muchii[200005];
void build(int nod)
{
    nr[nod]=1;
    for(int i:muchii[nod])
    {
        int a=G[i].a,b=G[i].b;
        int x=(a^b^nod);
        if(!edgeuse[i]&&x!=par[nod])
        {
            par[x]=nod;
            build(x);
            nr[nod]+=nr[x];
        }
    }
}
void reroot(int nod,int fiu)
{
    nr[nod]-=nr[fiu];
    nr[fiu]+=nr[nod];
    par[fiu]=0;
    par[nod]=fiu;
}
int findcentroid(int nod)
{
    par[nod]=0;
    build(nod);
    bool found=0;
    while(!found)
    {
        found=1;
        for(int i:muchii[nod])
            if(!edgeuse[i])
            {
                int a=G[i].a,b=G[i].b;
                int x=(a^b^nod);
                if(nr[x]>nr[nod]/2)
                {
                    reroot(nod,x);
                    nod=x;
                    found=0;
                    break;
                }
            }
    }
    return nod;
}
void dfs(int nod)
{
    if(dist[nod]==k)
        ans=min(ans,niv[nod]);
    for(int i:muchii[nod])
        if(!edgeuse[i])
        {
            int a=G[i].a,b=G[i].b;
            int x=(a^b^nod);
            if(x!=par[nod])
            {
                par[x]=nod;
                niv[x]=niv[nod]+1;
                dist[x]=dist[nod]+G[i].cost;
                dfs(x);
            }
        }
}
void dfs1(int nod)
{
    if(dist[nod]<k&&dist[nod]>0)
    {
        vals.push_back(dist[nod]);
        mini[dist[nod]]=min(1LL*mini[dist[nod]],niv[nod]);
    }
    for(int i:muchii[nod])
        if(!edgeuse[i])
        {
            int a=G[i].a,b=G[i].b;
            int x=(a^b^nod);
            if(par[nod]!=x)
                dfs1(x);
        }
}
void go(int nod)
{
    int root=findcentroid(nod);
    dist[root]=0;
    niv[root]=0;
    par[root]=0;
    dfs(root);
    allvals.clear();
    for(int i:muchii[root])
        if(!edgeuse[i])
        {
            vals.clear();
            int a=G[i].a,b=G[i].b;
            int x=(a^b^root);
            dfs1(x);
            sort(vals.begin(),vals.end());
            vals.erase(unique(vals.begin(),vals.end()),vals.end());
            vector<pii> mine;
            for(int j:vals)
            {
                if(mini[j]<m1[j])
                {
                    m2[j]=m1[j];
                    m1[j]=mini[j];
                }
                else if(mini[j]<m2[j])
                    m2[j]=mini[j];
                mine.push_back({j,mini[j]});
                mini[j]=1e9;
            }
            allvals.push_back(mine);
        }
    for(auto v:allvals)
    {
        for(pii a:v)
            mini[a.first]=a.second;
        for(pii a:v)
        {
            int need=k-a.first;
            if(need==0||need==k)
                continue;
            ll val=a.second;
            if(m1[need]==mini[need])
                val+=m2[need];
            else
                val+=m1[need];
            ans=min(ans,val);
        }
        for(pii a:v)
            mini[a.first]=1e9;
    }
    for(auto v:allvals)
    {
        for(pii a:v)
            m1[a.first]=m2[a.first]=1e9;
    }
    for(int i:muchii[root])
        if(!edgeuse[i])
        {
            edgeuse[i]=1;
            int a=G[i].a,b=G[i].b;
            int x=(a^b^root);
            go(x);
        }
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N;
    k=K;
    for(int i=1;i<=k;i++)
    {
        m1[i]=m2[i]=1e9;
        mini[i]=1e9;
    }
    for(int i=0;i<n-1;i++)
    {
        int a=H[i][0];
        int b=H[i][1];
        a++;
        b++;
        G[i+1]={a,b,0};
        muchii[a].push_back(i+1);
        muchii[b].push_back(i+1);
    }
    for(int i=0;i<n-1;i++)
        G[i+1].cost=L[i];
    go(1);
    if(ans<=n)
        return ans;
    return -1;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 5024 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 4 ms 5024 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 4 ms 5204 KB Output is correct
22 Correct 9 ms 15920 KB Output is correct
23 Correct 11 ms 14044 KB Output is correct
24 Correct 9 ms 15316 KB Output is correct
25 Correct 9 ms 15060 KB Output is correct
26 Correct 6 ms 9192 KB Output is correct
27 Correct 9 ms 14508 KB Output is correct
28 Correct 5 ms 7508 KB Output is correct
29 Correct 6 ms 8916 KB Output is correct
30 Correct 6 ms 9428 KB Output is correct
31 Correct 8 ms 12884 KB Output is correct
32 Correct 9 ms 13524 KB Output is correct
33 Correct 10 ms 14292 KB Output is correct
34 Correct 7 ms 12144 KB Output is correct
35 Correct 8 ms 14676 KB Output is correct
36 Correct 9 ms 16084 KB Output is correct
37 Correct 8 ms 14548 KB Output is correct
38 Correct 7 ms 11092 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 5024 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 4 ms 5024 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 351 ms 16376 KB Output is correct
20 Correct 314 ms 16392 KB Output is correct
21 Correct 356 ms 16492 KB Output is correct
22 Correct 255 ms 16692 KB Output is correct
23 Correct 182 ms 16548 KB Output is correct
24 Correct 109 ms 16588 KB Output is correct
25 Correct 283 ms 20172 KB Output is correct
26 Correct 127 ms 22852 KB Output is correct
27 Correct 336 ms 28400 KB Output is correct
28 Correct 728 ms 40360 KB Output is correct
29 Correct 697 ms 39604 KB Output is correct
30 Correct 333 ms 28236 KB Output is correct
31 Correct 334 ms 28304 KB Output is correct
32 Correct 456 ms 28440 KB Output is correct
33 Correct 507 ms 28052 KB Output is correct
34 Correct 474 ms 28620 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 5024 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5020 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 4 ms 5024 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 4 ms 5204 KB Output is correct
22 Correct 9 ms 15920 KB Output is correct
23 Correct 11 ms 14044 KB Output is correct
24 Correct 9 ms 15316 KB Output is correct
25 Correct 9 ms 15060 KB Output is correct
26 Correct 6 ms 9192 KB Output is correct
27 Correct 9 ms 14508 KB Output is correct
28 Correct 5 ms 7508 KB Output is correct
29 Correct 6 ms 8916 KB Output is correct
30 Correct 6 ms 9428 KB Output is correct
31 Correct 8 ms 12884 KB Output is correct
32 Correct 9 ms 13524 KB Output is correct
33 Correct 10 ms 14292 KB Output is correct
34 Correct 7 ms 12144 KB Output is correct
35 Correct 8 ms 14676 KB Output is correct
36 Correct 9 ms 16084 KB Output is correct
37 Correct 8 ms 14548 KB Output is correct
38 Correct 7 ms 11092 KB Output is correct
39 Correct 351 ms 16376 KB Output is correct
40 Correct 314 ms 16392 KB Output is correct
41 Correct 356 ms 16492 KB Output is correct
42 Correct 255 ms 16692 KB Output is correct
43 Correct 182 ms 16548 KB Output is correct
44 Correct 109 ms 16588 KB Output is correct
45 Correct 283 ms 20172 KB Output is correct
46 Correct 127 ms 22852 KB Output is correct
47 Correct 336 ms 28400 KB Output is correct
48 Correct 728 ms 40360 KB Output is correct
49 Correct 697 ms 39604 KB Output is correct
50 Correct 333 ms 28236 KB Output is correct
51 Correct 334 ms 28304 KB Output is correct
52 Correct 456 ms 28440 KB Output is correct
53 Correct 507 ms 28052 KB Output is correct
54 Correct 474 ms 28620 KB Output is correct
55 Correct 19 ms 6356 KB Output is correct
56 Correct 18 ms 6228 KB Output is correct
57 Correct 159 ms 16496 KB Output is correct
58 Correct 53 ms 21800 KB Output is correct
59 Correct 176 ms 26100 KB Output is correct
60 Correct 813 ms 54120 KB Output is correct
61 Correct 360 ms 28748 KB Output is correct
62 Correct 388 ms 40972 KB Output is correct
63 Correct 568 ms 41068 KB Output is correct
64 Correct 1353 ms 36264 KB Output is correct
65 Correct 699 ms 28752 KB Output is correct
66 Correct 865 ms 49436 KB Output is correct
67 Correct 192 ms 51464 KB Output is correct
68 Correct 557 ms 41116 KB Output is correct
69 Correct 579 ms 41472 KB Output is correct
70 Correct 502 ms 40096 KB Output is correct