oj.uz

Submission #49439

# Submission time Handle Problem Language Result Execution time Memory
49439 2018-05-29T00:47:02 Z ho94949 Race (IOI11_race) C++17
0 / 100
 49 ms 52884 KB 
#include "race.h"
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
const int MAXN = 202020;
const int MAXK = 1010101;

int N, K;
vector<pair<int, int> > conn[MAXN];
bool visit_centroid[MAXN];

//solve for one vertex
namespace solver
{

set<int> used;
map<int, int> V[MAXK];

//added color & weight
void dfs(int a, int pa, int c, int len, int depth)
{
    if(len>K) return;
    
    used.insert(len);
    V[len][c] = depth;
    
    for(auto tmp: conn[a])
    {
        int x, w; tie(x, w) = tmp;
        if(visit_centroid[x] || x == pa) continue;
        dfs(x, a, c, len + w, depth+1);
    }
}

int solve(int a) 
{
    
    int tp = 0;
    for(auto tmp: conn[a])
    {
        int x, w; tie(x, w) = tmp;
        if(visit_centroid[x]) continue;
        dfs(x, a, ++tp, w, 1);
    }
    used.insert(0);
    V[0][-1] = 0;
    
    int ans = N;
    for(int x: used)
    {
        pair<int, int> min1(N, 0), min2(N, 0);
        for(auto y: V[x])
        {
            auto yrev = make_pair(y.second, y.first);
            if(min1 > yrev)
            {
                min2 = min1;
                min1 = yrev;
            }
            else if(min2 > yrev) min2 = yrev;
        }
        for(auto y: V[K-x])
        {
            if(y.first != min1.second)
                ans = min(ans, y.second+min1.first);
            if(y.first != min2.second)
                ans = min(ans, y.second+min2.first);
        }
    }
    
    //cleanup
    for(int x: used) V[x].clear();
    used.clear();
    
    return ans;
}


}

//context getting centroid
namespace centroid
{
int size[MAXN];
int max_subsize[MAXN];
vector<int> subtree;
void dfs(int a, int pa)
{
    subtree.push_back(a);
    size[a] = 1; max_subsize[a] = 0;
    for(auto tmp: conn[a])
    {
        int x, _; tie(x, _) = tmp;
        if(visit_centroid[x] || x == pa) continue;
        dfs(x, a);
        size[a] += size[x];
        max_subsize[a] = max(max_subsize[a], size[x]);
    }
}
int get_centroid(int x)
{
    subtree.clear();
    dfs(x, -1);
    int minv = subtree.size();
    int mini = -1;
    for(auto y: subtree)
    {
        int v = max((int)subtree.size()-size[y], max_subsize[y]);
        if(minv > v)
        {
            minv = v;
            mini = y;
        }
    }
    return mini;
}
}

int best_path(int _N, int _K, int H[][2], int L[])
{
    N = _N; K = _K;
    for(int i=0; i<N-1; ++i)
    {
        int s = H[i][0], e = H[i][1], x = L[i];
        conn[s].emplace_back(e, x);
        conn[e].emplace_back(s, x);
    }
    int ans = N;
    queue<int> Q;
    Q.push(0);
    while(!Q.empty())
    {
        int v = centroid::get_centroid(Q.front()); Q.pop();
        ans = min(ans, solver::solve(v));
        visit_centroid[v] = true;
        for(auto x: conn[v])
            if(!visit_centroid[x.first])
                Q.push(x.first);
    }
    if(ans == N) ans = -1;
    return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 52472 KB Output is correct
2 Correct 49 ms 52584 KB Output is correct
3 Correct 43 ms 52688 KB Output is correct
4 Correct 46 ms 52780 KB Output is correct
5 Correct 46 ms 52780 KB Output is correct
6 Correct 44 ms 52832 KB Output is correct
7 Correct 42 ms 52844 KB Output is correct
8 Correct 44 ms 52844 KB Output is correct
9 Correct 45 ms 52844 KB Output is correct
10 Correct 44 ms 52884 KB Output is correct
11 Correct 45 ms 52884 KB Output is correct
12 Correct 44 ms 52884 KB Output is correct
13 Correct 42 ms 52884 KB Output is correct
14 Incorrect 44 ms 52884 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 52472 KB Output is correct
2 Correct 49 ms 52584 KB Output is correct
3 Correct 43 ms 52688 KB Output is correct
4 Correct 46 ms 52780 KB Output is correct
5 Correct 46 ms 52780 KB Output is correct
6 Correct 44 ms 52832 KB Output is correct
7 Correct 42 ms 52844 KB Output is correct
8 Correct 44 ms 52844 KB Output is correct
9 Correct 45 ms 52844 KB Output is correct
10 Correct 44 ms 52884 KB Output is correct
11 Correct 45 ms 52884 KB Output is correct
12 Correct 44 ms 52884 KB Output is correct
13 Correct 42 ms 52884 KB Output is correct
14 Incorrect 44 ms 52884 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 52472 KB Output is correct
2 Correct 49 ms 52584 KB Output is correct
3 Correct 43 ms 52688 KB Output is correct
4 Correct 46 ms 52780 KB Output is correct
5 Correct 46 ms 52780 KB Output is correct
6 Correct 44 ms 52832 KB Output is correct
7 Correct 42 ms 52844 KB Output is correct
8 Correct 44 ms 52844 KB Output is correct
9 Correct 45 ms 52844 KB Output is correct
10 Correct 44 ms 52884 KB Output is correct
11 Correct 45 ms 52884 KB Output is correct
12 Correct 44 ms 52884 KB Output is correct
13 Correct 42 ms 52884 KB Output is correct
14 Incorrect 44 ms 52884 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 52472 KB Output is correct
2 Correct 49 ms 52584 KB Output is correct
3 Correct 43 ms 52688 KB Output is correct
4 Correct 46 ms 52780 KB Output is correct
5 Correct 46 ms 52780 KB Output is correct
6 Correct 44 ms 52832 KB Output is correct
7 Correct 42 ms 52844 KB Output is correct
8 Correct 44 ms 52844 KB Output is correct
9 Correct 45 ms 52844 KB Output is correct
10 Correct 44 ms 52884 KB Output is correct
11 Correct 45 ms 52884 KB Output is correct
12 Correct 44 ms 52884 KB Output is correct
13 Correct 42 ms 52884 KB Output is correct
14 Incorrect 44 ms 52884 KB Output isn't correct
15 Halted 0 ms 0 KB -