oj.uz

Submission #49438

# Submission time Handle Problem Language Result Execution time Memory
49438 2018-05-29T00:43:17 Z ho94949 Race (IOI11_race) C++17
0 / 100
 50 ms 52708 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);
    }
    
    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 47 ms 52600 KB Output is correct
2 Correct 43 ms 52652 KB Output is correct
3 Correct 48 ms 52684 KB Output is correct
4 Correct 47 ms 52684 KB Output is correct
5 Correct 50 ms 52684 KB Output is correct
6 Correct 47 ms 52684 KB Output is correct
7 Correct 47 ms 52684 KB Output is correct
8 Incorrect 46 ms 52708 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 52600 KB Output is correct
2 Correct 43 ms 52652 KB Output is correct
3 Correct 48 ms 52684 KB Output is correct
4 Correct 47 ms 52684 KB Output is correct
5 Correct 50 ms 52684 KB Output is correct
6 Correct 47 ms 52684 KB Output is correct
7 Correct 47 ms 52684 KB Output is correct
8 Incorrect 46 ms 52708 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 52600 KB Output is correct
2 Correct 43 ms 52652 KB Output is correct
3 Correct 48 ms 52684 KB Output is correct
4 Correct 47 ms 52684 KB Output is correct
5 Correct 50 ms 52684 KB Output is correct
6 Correct 47 ms 52684 KB Output is correct
7 Correct 47 ms 52684 KB Output is correct
8 Incorrect 46 ms 52708 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 52600 KB Output is correct
2 Correct 43 ms 52652 KB Output is correct
3 Correct 48 ms 52684 KB Output is correct
4 Correct 47 ms 52684 KB Output is correct
5 Correct 50 ms 52684 KB Output is correct
6 Correct 47 ms 52684 KB Output is correct
7 Correct 47 ms 52684 KB Output is correct
8 Incorrect 46 ms 52708 KB Output isn't correct
9 Halted 0 ms 0 KB -