oj.uz

Submission #1113052

# Submission time Handle Problem Language Result Execution time Memory
1113052 2024-11-15T14:31:47 Z Matkap Race (IOI11_race) C++17
0 / 100
 3000 ms 4944 KB 
/*
    Author:Matkap(prefix_sum)
*/
#include "race.h"
#include <bits/stdc++.h>
#include <array>

using namespace std;
#define endl "\n"
#define ar array
#define all(x) x.begin(),x.end()

const int INF = 1e17 , MOD = 1e9 + 7;

const int mxN = 2e5 + 7;
vector<ar<int,2>> adj[mxN];
int rem[mxN];
int sub[mxN];
int ans = INF;
int k1;
int find_subtree_size(int pos,int par = -1)
{
    sub[pos] = 1;
    for(auto [it, dist] : adj[pos])
    {
        if(it == par || rem[it]) continue;
        sub[pos] += find_subtree_size(it, pos);
    }
    return sub[pos];
}
int find_centroid(int sub_size, int pos,int par = -1)
{
    for(auto [it, dist] : adj[pos])
    {
        if(it == par || rem[it]) continue;
        if(sub[it] > sub_size / 2) return find_centroid(sub_size, it, pos);
    }
    return pos;
}
void solve(int pos,int par,int cur_path, int depth = 1)
{
    if(cur_path > k1) return;
    if(cur_path == k1)
    {
        ans = min(ans, depth);
    }
    for(auto [it, dist] : adj[pos])
    {
        if(rem[it]) continue;
        solve(it,pos,cur_path + dist,depth + 1);
    }
}
void build_decomp(int pos)
{
    int centroid = find_centroid(find_subtree_size(pos), pos);
    rem[centroid] = 1;
    for(auto [it, dist] : adj[centroid])
    {
        if(!rem[it])
        {
            solve(it,-1,dist);
        }
    }
    for(auto [it, dist] : adj[centroid])
    {
        if(rem[it]) continue;
        build_decomp(it);
    }
}
int best_path(int n,int k, int h[][2], int l[])
{
    k1 = k;
    for(int i = 0;n - 1 > i;i++)
    {
        adj[h[i][0]].push_back({h[i][1], l[i]});
        adj[h[i][0]].push_back({h[i][0], l[i]});
    }
    build_decomp(0);
    if(ans == INF) return -1;
    return ans;
}

Compilation message

race.cpp:13:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
   13 | const int INF = 1e17 , MOD = 1e9 + 7;
      |                 ^~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 4944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 4944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 4944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 4944 KB Time limit exceeded
2 Halted 0 ms 0 KB -