oj.uz

Submission #552873

# Submission time Handle Problem Language Result Execution time Memory
552873 2022-04-24T08:46:22 Z beedle Race (IOI11_race) C++17
43 / 100
 3000 ms 69792 KB 
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#define pi 3.141592653589793238
#define ll long long
#define ld long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 998244353ll
#define INF 1000000000000000000
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)

using namespace std;

void setup(int v, int p, int width[], vector <pair<int,int>> adj[])
{
    width[v]=1;
    for(auto u:adj[v])
    if(u.ff!=p)
    {
        setup(u.ff,v,width,adj);
        width[v]+=width[u.ff];
    }
}

int traverse(int n, int v, int p, int width[], vector <pair<int,int>> adj[])
{
    int outlier=-1;
    for(auto u:adj[v])
    if(u.ff!=p)
    if(width[u.ff]>n/2)
    outlier=u.ff;

    if(outlier==-1)
    return v;
    else 
    return traverse(n,outlier,v,width,adj);
}

void dfs(int v, int p, int k, int &ans, vector <int> &mydist, vector <int> &minlen, vector <int> &minlenothers, vector <pair<int,int>> adj[], int depth, vector <int> &ch)
{
    if(mydist[v]<=k)
    {
        int d=mydist[v];
        minlen[d]=min(minlen[d],depth);

        if(d==k)
        ans=min(ans,minlen[d]);

        ans=min(ans,depth+minlenothers[k-d]);

        ch.push_back(d);
    }

    for(auto u:adj[v])
    if(u.ff!=p)
    {
        mydist[u.ff]=mydist[v]+u.ss;
        dfs(u.ff,v,k,ans,mydist,minlen,minlenothers,adj, depth+1, ch);
    }
}

void find_children(int v, int p, vector <int> &ch, vector <pair<int,int>> adj[])
{
    ch.push_back(v);
    for(auto u:adj[v])
    if(u.ff!=p)
    find_children(u.ff,v,ch,adj);
}

int solve(int n, int k, vector <pair<int,int>> adj[])
{
    if(n==1)
    return mod;

    int width[n+1];
    setup(1,-1,width, adj);

    int v=traverse(n, 1,-1,width,adj);

    // cout<<"SETUP DONE: "<<v<<endl;

    vector <int> minlenothers(k+1,mod);
    vector <int> mydist(n+1,mod);
    vector <int> minlen(k+1,mod);
    int ans=mod;
    vector <int> ch;

    for(auto u:adj[v])
    {
        mydist[u.ff]=u.ss;
        dfs(u.ff,v,k,ans,mydist,minlen,minlenothers,adj,1,ch);

        for(auto x:ch)
        {
            minlenothers[x]=min(minlenothers[x],minlen[x]);
            minlen[x]=mod;
        }

        ch.clear();
    }

    // cout<<"ANS : "<<ans<<endl;

    for(auto u:adj[v])
    {
        find_children(u.ff,v,ch,adj);

        sort(all(ch));
        ll s=sz(ch);
        vector <int> m(n+1);
        rep(i,0,s-1)
        m[ch[i]]=i+1;

        vector <pair<int,int>> nadj[s+1];

        rep(i,0,s-1)
        {
            int vt=ch[i];
            for(auto u:adj[vt])
            if(u.ff!=v)
            {
                nadj[m[vt]].pb({m[u.ff],u.ss});
            }
        }

        ch.clear();

        // cout<<"IN "<<n<<endl;
        // cout<<s<<" "<<k<<endl;
        // rep(i,1,s)
        // {
        //     cout<<i<<" -> ";
        //     for(auto x:nadj[i])
        //     {
        //         cout<<x.ff<<","<<x.ss<<"  ";
        //     }
        //     cout<<endl;
        // }
        ans=min(ans,solve(s,k,nadj));
    }

    return ans;
}

int best_path(int n, int k, int h[][2], int l[])
{
    vector <pair<int,int>> adj[n+1];
    rep(i,0,n-2)
    {
        adj[h[i][0]+1].pb({h[i][1]+1,l[i]});
        adj[h[i][1]+1].pb({h[i][0]+1,l[i]});
    }

    ll x=solve(n,k,adj);
    return (x==mod?-1:x);
}

// signed main()
// {
//     fast;

//     // freopen("milkorder.in","r",stdin);
//     // freopen("milkorder.out","w",stdout);

//     int n=11;
//     int k=12;
//     int h[10][2]={{0,1},{0,2},{2,3},{3,4},{4,5},{0,6},{6,7},{6,8},{8,9},{8,10}};
//     int l[10]={3,4,5,4,6,3,2,5,6,7};

//     cout<<best_path(n,k,h,l);

//     return 0;
// }

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 1486 ms 68960 KB Output is correct
23 Correct 741 ms 56540 KB Output is correct
24 Correct 684 ms 54612 KB Output is correct
25 Correct 968 ms 56704 KB Output is correct
26 Correct 456 ms 20380 KB Output is correct
27 Correct 1118 ms 53856 KB Output is correct
28 Correct 199 ms 13808 KB Output is correct
29 Correct 437 ms 23356 KB Output is correct
30 Correct 335 ms 25076 KB Output is correct
31 Correct 656 ms 43976 KB Output is correct
32 Correct 902 ms 53224 KB Output is correct
33 Correct 1186 ms 58736 KB Output is correct
34 Correct 985 ms 44624 KB Output is correct
35 Correct 1175 ms 61200 KB Output is correct
36 Correct 1037 ms 69792 KB Output is correct
37 Correct 909 ms 59688 KB Output is correct
38 Correct 528 ms 38336 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 285 ms 14728 KB Output is correct
20 Correct 287 ms 15064 KB Output is correct
21 Correct 309 ms 15284 KB Output is correct
22 Correct 228 ms 14856 KB Output is correct
23 Correct 319 ms 14120 KB Output is correct
24 Correct 141 ms 10488 KB Output is correct
25 Correct 406 ms 21200 KB Output is correct
26 Correct 330 ms 21084 KB Output is correct
27 Correct 307 ms 17376 KB Output is correct
28 Correct 925 ms 41860 KB Output is correct
29 Correct 938 ms 41852 KB Output is correct
30 Correct 361 ms 17416 KB Output is correct
31 Correct 300 ms 17516 KB Output is correct
32 Correct 371 ms 17412 KB Output is correct
33 Correct 670 ms 28792 KB Output is correct
34 Correct 699 ms 26824 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 1486 ms 68960 KB Output is correct
23 Correct 741 ms 56540 KB Output is correct
24 Correct 684 ms 54612 KB Output is correct
25 Correct 968 ms 56704 KB Output is correct
26 Correct 456 ms 20380 KB Output is correct
27 Correct 1118 ms 53856 KB Output is correct
28 Correct 199 ms 13808 KB Output is correct
29 Correct 437 ms 23356 KB Output is correct
30 Correct 335 ms 25076 KB Output is correct
31 Correct 656 ms 43976 KB Output is correct
32 Correct 902 ms 53224 KB Output is correct
33 Correct 1186 ms 58736 KB Output is correct
34 Correct 985 ms 44624 KB Output is correct
35 Correct 1175 ms 61200 KB Output is correct
36 Correct 1037 ms 69792 KB Output is correct
37 Correct 909 ms 59688 KB Output is correct
38 Correct 528 ms 38336 KB Output is correct
39 Correct 285 ms 14728 KB Output is correct
40 Correct 287 ms 15064 KB Output is correct
41 Correct 309 ms 15284 KB Output is correct
42 Correct 228 ms 14856 KB Output is correct
43 Correct 319 ms 14120 KB Output is correct
44 Correct 141 ms 10488 KB Output is correct
45 Correct 406 ms 21200 KB Output is correct
46 Correct 330 ms 21084 KB Output is correct
47 Correct 307 ms 17376 KB Output is correct
48 Correct 925 ms 41860 KB Output is correct
49 Correct 938 ms 41852 KB Output is correct
50 Correct 361 ms 17416 KB Output is correct
51 Correct 300 ms 17516 KB Output is correct
52 Correct 371 ms 17412 KB Output is correct
53 Correct 670 ms 28792 KB Output is correct
54 Correct 699 ms 26824 KB Output is correct
55 Correct 38 ms 2216 KB Output is correct
56 Correct 27 ms 1736 KB Output is correct
57 Correct 263 ms 14124 KB Output is correct
58 Correct 1112 ms 9880 KB Output is correct
59 Execution timed out 3031 ms 46692 KB Time limit exceeded
60 Halted 0 ms 0 KB -