Submission #914866

#	Time	Username	Problem	Language	Result	Execution time	Memory
914866		StefanL2005	Race (IOI11_race)	C++14	0 / 100	1 ms	2648 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;
};

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)
{
    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);
    }
}

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

    int branch = 0;
    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, 1, node->Cost[i], All_Paths);
        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:{ 
                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.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);
    } 
}

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, NULL, 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;

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

    
}

void add_muchie(nod *A, int B, int cost, vector<nod*> &Tree)
{
    nod *C = new nod;
    C->nr = B;

    A->Ch.push_back(C);
    A->Cost.push_back(cost);
    C->Ch.push_back(A);
    C->Cost.push_back(cost);

    Tree[B] = C;
}

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

    for (int i = 0; i < n-1; i++)
    {
        if (H[i][1] < H[i][0])
            swap(H[i][1], H[i][0]);

        add_muchie(Tree[H[i][0]], H[i][1], L[i], Tree);
    }  

    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:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<nod*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < node->Ch.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'nod* Locate_Central(nod*, nod*, int, std::vector<int>&)':
race.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<nod*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 0; i < node->Ch.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void DFS_Paths(nod*, nod*, int, int, int, std::vector<path>&)':
race.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<nod*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i = 0; i < node->Ch.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void CalculatePaths(nod*, nod*, int, int&)':
race.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<nod*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < node->Ch.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
race.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<path>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int i = 0; i < All_Paths.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
race.cpp:111:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<path>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     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:146:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<nod*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for (int i = 0; i < center->Ch.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~
race.cpp:153:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<nod*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |         for (int j = 0; j < vecin->Ch.size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~

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