| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 577151 |
2022-06-14T07:57:04 Z |
web |
Dreaming (IOI13_dreaming) |
C++17 |
|
1000 ms |
20352 KB |
#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 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;
}
Compilation message
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::pair<int, int> lenPathClosestTo(std::vector<int>&, int, int)':
dreaming.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (int i = 0; i < distances.size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int i = 0; i < forest.size(); ++i)
| ~~^~~~~~~~~~~~~~~
dreaming.cpp:146:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int i = 1; i < diameterInfos.size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:151:27: 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]
151 | for (int k = 0; k < forest[get<2>(diameterInfos[i])].size(); ++k)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:122:9: warning: unused variable 'numTrees' [-Wunused-variable]
122 | int numTrees = forest.size();
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
20352 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
308 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
20352 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1079 ms |
17908 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
308 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
20352 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
