Submission #723141

#	Time	Username	Problem	Language	Result	Execution time	Memory
723141		sochu	Race (IOI11_race)	C++17	43 / 100	3039 ms	52804 KiB

race

    #include <bits/stdc++.h>

    using namespace std;

	const int N = 2e5 + 10;

    set < int > G[N];
    int sz[N];
    int a[N * 10];
    int H[N][2] , L[N];

    int K;

    void getsize(int node , int par)
    {
        sz[node] = 1;

        for(auto e : G[node])
        {
            int to = node ^ H[e][0] ^ H[e][1];
            int c = L[e];

            if(to != par)
            {
                getsize(to , node);
                sz[node] += sz[to];
            }
        }
    }

    int find(int node , int par , int n)
    {
        for(auto e : G[node])
        {
            int to = node ^ H[e][0] ^ H[e][1];
            int c = L[e];

            if(to != par)
            {
                if(sz[to] > n / 2)
                    return find(to , node , n);
            }
        }

        return node;
    }

    int ans = INT_MAX;

    void get(int node , int par , int len , int h)
    {
        if(len <= K && a[K - len])
            ans = min(ans , a[K - len] + h - 1);

      	if(len == K)
          ans = min(ans , h - 1);

        for(auto e : G[node])
        {
            int to = node ^ H[e][0] ^ H[e][1];
            int c = L[e];

            if(to != par)
                get(to , node , len + c , h + 1);
        }
    }

    void add(int node , int par , int len , int h)
    {
        if(len <= K)
        {
            if(a[len] == 0) a[len] = h - 1;
            else a[len] = min(a[len] , h - 1);
        }

        for(auto e : G[node])
        {
            int to = node ^ H[e][0] ^ H[e][1];
            int c = L[e];

            if(to != par)
                add(to , node , len + c , h + 1);
        }
    }

    void solve(int root)
    {
        for(int i = 0 ; i <= K ; i++)
            a[i] = 0;

        for(auto e : G[root])
        {
            int to = root ^ H[e][0] ^ H[e][1];
            int c = L[e];

            get(to , root , c , 2);
            add(to , root , c , 2);
        }
    }

    void decomp(int root)
    {
        getsize(root , 0);
        int c = find(root , 0 , sz[root]);
        solve(c);

        for(auto e : G[c])
        {
            int to = c ^ H[e][0] ^ H[e][1];
            G[to].erase(e);
            decomp(to);
        }
    }


    int best_path(int n , int k , int h[][2] , int l[])
    {
        K = k;

        for(int i = 0 ; i < n - 1 ; i++)
        {
            H[i][0] = h[i][0];
            H[i][1] = h[i][1];
            L[i] = l[i];
        }

        for(int i = 0 ; i < n - 1 ; i++)
        {
            int x = H[i][0];
            int y = H[i][1];

            G[x].insert(i);
            G[y].insert(i);
        }

        decomp(0);
        if(ans == INT_MAX) ans = -1;
        return ans;
    }

Compilation message (stderr)

race.cpp: In function 'void getsize(int, int)':
race.cpp:21:17: warning: unused variable 'c' [-Wunused-variable]
   21 |             int c = L[e];
      |                 ^
race.cpp: In function 'int find(int, int, int)':
race.cpp:36:17: warning: unused variable 'c' [-Wunused-variable]
   36 |             int c = L[e];
      |                 ^

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