Submission #578515

#	Time	Username	Problem	Language	Result	Execution time	Memory
578515		web	Dreaming (IOI13_dreaming)	C++17	10 / 100	1074 ms	20356 KiB

dreaming

#include <iostream>
#include <climits>
#include <algorithm>
#include <unordered_map>
#include "dreaming.h"
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
using namespace std;


unordered_set<int> DFS_findTree(int currNode, int parentNode, bitset<100000>& visited ,  vector<vector<pair<int, int>>>& adjList)
{
    unordered_set<int> retVal = {currNode};
    visited.set(currNode);
    for(pair<int,int> neigh : adjList[currNode])
    {
        if(neigh.first == parentNode)
            continue;
        else
        {
            unordered_set<int> r = DFS_findTree(neigh.first, currNode, visited, adjList);
            for(auto i : r)
                retVal.insert(i);
        }
    }
    return retVal;
}

void findTrees(vector<vector<vector<pair<int, int>>>>& forest, vector<vector<pair<int, int>>>& adjList)
{
    bitset<100000> visited;
    
    for(int i  =0;i <adjList.size(); ++i)
    {
        if(!visited.test(i))
        {
            unordered_set<int> tree = DFS_findTree(i, -1, visited, adjList);
            vector<vector<pair<int,int>>> newAdjlist(tree.size());
            int index = 0;
            unordered_map<int,int> m;
            for(int node :tree)
            {
                m[node] = index;
                ++index;
            }
            for(int node :tree)
            {
                for(int k = 0; k<adjList[node].size(); ++k)
                {
                    newAdjlist[m[node]].push_back({m[adjList[node][k].first], adjList[node][k].second});
                }
            }
            forest.push_back(newAdjlist);
        }
    }
    return;
    
}

void old_DFSforDistances(vector<vector<pair<int,int>>>& tree, int currNode, int parent,
    vector<long long>& distances, long long weightTravelled)
{
   // cout << "entering node " << currNode << " from " << parent << endl;
    if(currNode == parent)
    {
        distances[currNode] =0;
    }
    else
    {
        if(parent != -1)
            distances[currNode] = weightTravelled + distances[parent];
    }
    for(pair<int,int> node : tree[currNode])
    {
        if(node.first == parent)
            continue;
        old_DFSforDistances(tree, node.first, currNode, distances, node.second);
        
    }
    return;
}


vector<int> old_diameterOfTree(vector<vector<pair<int,int>>>& tree)
{
    vector<int> distancesRound1(tree.size());
   // DFSforDistances(tree, 0, 0, distancesRound1, 0);
    int node1 = max_element(distancesRound1.begin(), distancesRound1.end())-distancesRound1.begin();
    //DFSforDistances(tree, node1,node1, distancesRound1, 0);
    return distancesRound1;
}

pair<int,int> old_lenPathClosestTo(vector<int> & distances, int wantLen, int maxDist)
{
  //  vector<int> distances = diameterOfTree(tree);
    //best sol 
   // int trueDiam = *(max_element(distances.begin(), distances.end()));
    int bestTheorDist = wantLen;// (1 + trueDiam) / 2;
    int nodeIndexBestDist = 0, bestDist = INT_MAX;
    for (int i = 0; i < distances.size(); ++i)
    {
        if (abs(distances[i] - bestTheorDist) < bestDist)
        {
            nodeIndexBestDist = i;
            bestDist = abs(distances[i] - bestTheorDist);
        }
    }
    return {max(maxDist - bestDist, bestDist), nodeIndexBestDist };
}

void DFS_to_Furthest(vector<vector<pair<int, int>>>& tree, int curr, int parent, long long currW,  vector<long long>& distances, vector<int>& parents)
{
    parents[curr] = parent;
   // cout << "at node " << curr << endl;
    for (pair<int,int> node : tree[curr])
    {
   //     cout << "child: " << node.first<<" with edge "<< node.second << endl;
        if (node.first == parent)
            continue;
        else
        {
            distances[node.first] = currW + node.second;
            DFS_to_Furthest(tree, node.first, curr, currW + node.second, distances, parents);
        }
    }
    
}
class Rope
{
public:
    vector<long long> distancesFromStart;
    long long totalLen;
    long long longHalf;
    long long shortHalf;
    
    Rope(vector<vector<pair<int, int>>>& tree)
    {
        int numNodesInitial = tree.size();
        vector<long long> distances(numNodesInitial);
        old_DFSforDistances(tree, 0, -1, distances, 0);
        int node1 = max_element(distances.begin(), distances.end()) - distances.begin();
        vector<int> parents(numNodesInitial);
        DFS_to_Furthest(tree, node1, -1, 0, distances, parents);
        int node2 = max_element(distances.begin(), distances.end()) - distances.begin();
       
        while (node2 != node1)
        {
            distancesFromStart.push_back(distances[node2]);
            node2 = parents[node2];
        } 
        distancesFromStart.push_back(0);
       
        totalLen = distancesFromStart[0];
        auto possHalf  =
            lower_bound(distancesFromStart.rbegin(), distancesFromStart.rend(), (totalLen + 1) / 2);
        if(possHalf == distancesFromStart.rbegin())
        {
            longHalf = max(*possHalf, totalLen - (*possHalf));
        }
        else
        {
            if (possHalf == distancesFromStart.rend())
            {
                longHalf = max(*(possHalf - 1), totalLen - (*(possHalf - 1)));
            }
            else {
                auto possHalf2 = possHalf - 1;
                if (abs(*possHalf - (totalLen + 1) / 2) > abs(*possHalf2 - (totalLen + 1) / 2))
                {
                    possHalf = possHalf2;
                }
                longHalf = max(*possHalf, totalLen - (*possHalf));
            }
        }

        shortHalf = totalLen - longHalf;
      //  print();
    }
    void print()
    {
        cout << "Rope: " << endl;
        cout << "Total Length: " << totalLen<<endl;
        cout << "Sizes of Ends: " << longHalf << " " << shortHalf << endl;
    }
};


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vector<vector<pair<int, int>>> adjList(N);
    for (int i = 0; i < M; ++i)
    {
        adjList[A[i]].push_back({ B[i], T[i] });
        adjList[B[i]].push_back({ A[i], T[i] });
    }
    vector<vector<vector<pair<int, int>>>> forest;
    findTrees(forest, adjList);
    //calc diameter of every tree
    int numTrees = forest.size();
    
    Rope currRope(forest[0]);
//currRope.print();
    for (int i = 1; i < numTrees; ++i)
    {
       Rope newRope(forest[i]);
      
        if (newRope.longHalf + L <= currRope.shortHalf)
            continue;
        else
        {
            if (newRope.shortHalf >= currRope.longHalf + L)
            {
                swap(newRope, currRope);
                continue;
            }
            else
            {
                long long newTotalLen = currRope.longHalf + L + newRope.longHalf;
                long long newHalfLen = 0;
                if ((newTotalLen + 1) / 2 > currRope.longHalf)
                {
                    //search in other rope
                    long long numToSearchFor = ((newTotalLen + 1) / 2) - L - currRope.longHalf;
                    auto test = lower_bound(newRope.distancesFromStart.rbegin(),
                        newRope.distancesFromStart.rend(), numToSearchFor);
                    if (test == newRope.distancesFromStart.rbegin())
                    {
                        if (abs(currRope.longHalf - (newTotalLen + 1) / 2) < (*test - numToSearchFor))
                        {
                            newHalfLen = currRope.longHalf;
                        }
                        else
                        {
                            newHalfLen = currRope.longHalf + L;
                        }
                    }
                    else
                    {
                        newHalfLen = *test + currRope.longHalf + L;
                    }
                }
                else
                {
                    newHalfLen = currRope.longHalf;
                }

                currRope.longHalf = max(newHalfLen, newTotalLen - newHalfLen);
                currRope.shortHalf = newTotalLen - currRope.longHalf;
                currRope.totalLen = newTotalLen;
                continue;


            }
        }
    }

   // cout << currRope.totalLen << endl;
    



    /*
    //vector<int> distances(N);// diameterOfTree(forest[0]);
 //   int currTotalDiameter = 0;// *(max_element(distances.begin(), distances.end()));
   // int centerPieceDist = 0, centerPieceIndex = 0;// lenPathClosestTo(distances, (currTotalDiameter + 1) / 2);

    vector<tuple<int, pair<int, int>, int>> diameterInfos(forest.size());
    vector<vector<int>> distancesOfTrees(N);
    for (int i = 0; i < forest.size(); ++i)
    {
        distancesOfTrees[i] = diameterOfTree(forest[i]);
        get<0>(diameterInfos[i]) = *(max_element(distancesOfTrees[i].begin(), distancesOfTrees[i].end()));
        get<1>(diameterInfos[i]) =
            lenPathClosestTo(distancesOfTrees[i], (get<0>(diameterInfos[i]) + 1) / 2, get<0>(diameterInfos[i]));
        get<2>(diameterInfos[i]) = i;
    }
    sort(diameterInfos.rbegin(), diameterInfos.rend());
    

    vector<vector<pair<int, int>>> finalTree = forest[get<2>(diameterInfos[0])];
    int finalTreeTotalDiam = get<0>(diameterInfos[0]);
    vector<int> finalDistances = distancesOfTrees[get<2>(diameterInfos[0])];
    pair<int, int> midPFinalTree = get<1>(diameterInfos[0]);
    for (int i = 1; i < diameterInfos.size(); ++i)
    {
        //merge trees
        int finalTreeInitialSize = finalTree.size();
        
        for (int k = 0; k < forest[get<2>(diameterInfos[i])].size(); ++k)
        {
            for_each(forest[get<2>(diameterInfos[i])][k].begin(), forest[get<2>(diameterInfos[i])][k].end(),
                [finalTreeInitialSize](pair<int,int>& n) { n.first += finalTreeInitialSize; });
            finalTree.push_back(forest[get<2>(diameterInfos[i])][k]);
        }
        finalTree[midPFinalTree.second].push_back({ get<1>(diameterInfos[i]).second+ finalTreeInitialSize, L });
        finalTree[finalTreeInitialSize + get<1>(diameterInfos[i]).second].push_back({ midPFinalTree.second, L });
        finalDistances = diameterOfTree(finalTree);
       finalTreeTotalDiam = *(max_element(finalDistances.begin(), finalDistances.end()));
       midPFinalTree = lenPathClosestTo(finalDistances, (finalTreeTotalDiam + 1) / 2, finalTreeTotalDiam);
       
    }
   
    */
    return currRope.totalLen;
}

Compilation message (stderr)

dreaming.cpp: In function 'void findTrees(std::vector<std::vector<std::vector<std::pair<int, int> > > >&, std::vector<std::vector<std::pair<int, int> > >&)':
dreaming.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i  =0;i <adjList.size(); ++i)
      |                   ~~^~~~~~~~~~~~~~~
dreaming.cpp:50:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |                 for(int k = 0; k<adjList[node].size(); ++k)
      |                                ~^~~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'std::vector<int> old_diameterOfTree(std::vector<std::vector<std::pair<int, int> > >&)':
dreaming.cpp:90:9: warning: unused variable 'node1' [-Wunused-variable]
   90 |     int node1 = max_element(distancesRound1.begin(), distancesRound1.end())-distancesRound1.begin();
      |         ^~~~~
dreaming.cpp: In function 'std::pair<int, int> old_lenPathClosestTo(std::vector<int>&, int, int)':
dreaming.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i = 0; i < distances.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 10 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23