| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 577150 | web | Dreaming (IOI13_dreaming) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#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 DFSforDistances(vector<vector<pair<int,int>>>& tree, int currNode, int parent, vector<int>& distances, int weightTravelled)
{
// cout << "entering node " << currNode << " from " << parent << endl;
if(currNode == parent)
{
distances[currNode] =0;
}
else
{
distances[currNode] = weightTravelled + distances[parent];
}
for(pair<int,int> node : tree[currNode])
{
if(node.first == parent)
continue;
DFSforDistances(tree, node.first, currNode, distances, node.second);
}
return;
}
vector<int> 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> 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 };
}
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();
//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 finalTreeTotalDiam;
}