Submission #915319

#	Time	Username	Problem	Language	Result	Execution time	Memory
915319		StefanL2005	Race (IOI11_race)	C++14	100 / 100	602 ms	83416 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define inf 1000*1000*1000
#define ll long long

struct nod{
    int nr;
    vector<nod*> Ch;
    vector<int> Cost;

    nod(){nr = 0;}
};

struct path{
    int br, sum, muchi;
};
vector<vector<path>> Sum;

void DFS_Descendants(nod *node, nod *p, vector<int> &desc)
{
    desc[node->nr] = 0;

    for (int i = 0; i < node->Ch.size(); i++)
    {
        auto vecin = node->Ch[i];

        if (vecin == p || vecin == 0)
            continue;
        DFS_Descendants(vecin, node, desc);
        desc[node->nr] += desc[vecin->nr];
    }

    desc[node->nr]++;
}

nod* Locate_Central(nod *node, nod *p, int size, vector<int> &desc)
{
    for (int i = 0; i < node->Ch.size(); i++)
    {
        auto vecin = node->Ch[i];
        
        if (vecin == p || vecin == 0)
            continue;
        
        if (desc[vecin->nr] > size/2)
        {
            desc[node->nr] -= desc[vecin->nr];
            desc[vecin->nr] += desc[node->nr];

            return Locate_Central(vecin, node, size, desc);
        }
    }

    return node;
}

void DFS_Paths(nod *node, nod *block, int branch, int p, int s, vector<path> &All_Paths, int k)
{
    if (s > k)
        return;
    path A; A.br = branch; A.sum = s; A.muchi = p;
    All_Paths.push_back(A);
    
    for (int i = 0; i < node->Ch.size(); i++)
    {
        auto vecin = node->Ch[i];
        if (vecin == block || vecin == 0)
            continue;

        DFS_Paths(vecin, node, branch, p + 1, s + node->Cost[i], All_Paths, k);
    }
}

void CalculatePaths(nod* node, int k, int &best)
{
    vector<path> All_Paths;

    int branch = 0;
    for (int i = 0; i < node->Ch.size(); i++)
    {
        auto vecin = node->Ch[i];
        if (vecin == 0)
            continue;
        
        DFS_Paths(vecin, node, branch, 1, node->Cost[i], All_Paths, k);
        branch++;
    }

    for (int i = 0; i < All_Paths.size(); i++)
    {
        auto A = All_Paths[i];

        if (A.sum > k)
            continue;
        switch(Sum[A.sum].size()) 
        {
            case 0:{ Sum[A.sum].push_back(A); break; }
            case 1:{ 
                if (A.br == Sum[A.sum][0].br)
                {
                    if (A.muchi < Sum[A.sum][0].muchi)
                        Sum[A.sum][0] = A;
                    break;
                }

                Sum[A.sum].push_back(A);
                if (Sum[A.sum][1].muchi < Sum[A.sum][0].muchi)
                    swap (Sum[A.sum][1], Sum[A.sum][0]);
            break; }

            default: {
                if (A.br == Sum[A.sum][0].br)
                {
                    if (A.muchi < Sum[A.sum][0].muchi)
                        Sum[A.sum][0] = A;
                    break;
                }

                if (A.muchi < Sum[A.sum][1].muchi)
                    Sum[A.sum][1] = A;
                if (Sum[A.sum][1].muchi < Sum[A.sum][0].muchi)
                    swap (Sum[A.sum][1], Sum[A.sum][0]);
            break; }
        }
    }

    for (int i = 0; i < All_Paths.size(); i++)
    {
        auto A = All_Paths[i];
        if (A.sum > k)
            continue;
        if (A.sum == k)
        {   
            best = min(best, A.muchi);
            continue;
        }
        if (Sum[k - A.sum].size() == 0)
            continue;

        auto B = Sum[k - A.sum][0];
        if (B.br == A.br)
        {
            if (Sum[B.sum].size() == 1)
                continue;
            B = Sum[B.sum][1];
        }
        
        best = min(best, A.muchi + B.muchi);
    }
    for (int i = 0; i < All_Paths.size(); i++)
        Sum[All_Paths[i].sum].clear();
}

void D_C (nod *root, int k, int size, vector<int> &desc, int &best)
{
    if (size == 1)
        return;

    nod *center;
    DFS_Descendants(root, NULL, desc);
    center = Locate_Central(root, NULL, size, desc);
    CalculatePaths(center, k, best);   

    for (int i = 0; i < center->Ch.size(); i++)
    {
        auto vecin = center->Ch[i];

        if (vecin == 0)
            continue;

        for (int j = 0; j < vecin->Ch.size(); j++)
            if (vecin->Ch[j] == center)
            { vecin->Ch[j] = NULL; break; }

        D_C(vecin, k, desc[vecin->nr], desc, best);
    }
}

int best_path(int n, int k, int H[][2], int L[])
{
    int best = inf;
    vector<int> desc(n, 0);
    vector<nod*> Tree(n);
    Sum.resize(k + 1);

    for (int i = 0; i < n; i++)
    { Tree[i] = new nod; Tree[i]->nr = i; }
    
    for (int i = 0; i < n-1; i++)
    {
        int A = H[i][0], B = H[i][1];
        Tree[A]->Ch.push_back(Tree[B]);
        Tree[B]->Ch.push_back(Tree[A]);
        Tree[A]->Cost.push_back(L[i]);
        Tree[B]->Cost.push_back(L[i]);
    }  

    D_C(Tree[0], k, n, desc, best);

    if (best == inf)
        return -1;
    return best;
}

Compilation message (stderr)

race.cpp: In function 'void DFS_Descendants(nod*, nod*, std::vector<int>&)':
race.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<nod*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 0; i < node->Ch.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'nod* Locate_Central(nod*, nod*, int, std::vector<int>&)':
race.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<nod*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0; i < node->Ch.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void DFS_Paths(nod*, nod*, int, int, int, std::vector<path>&, int)':
race.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<nod*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0; i < node->Ch.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void CalculatePaths(nod*, int, int&)':
race.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<nod*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0; i < node->Ch.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
race.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<path>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < All_Paths.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
race.cpp:127:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<path>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for (int i = 0; i < All_Paths.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
race.cpp:150:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<path>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for (int i = 0; i < All_Paths.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
race.cpp: In function 'void D_C(nod*, int, int, std::vector<int>&, int&)':
race.cpp:164:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<nod*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for (int i = 0; i < center->Ch.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~
race.cpp:171:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<nod*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |         for (int j = 0; j < vecin->Ch.size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~

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