| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 578515 |
2022-06-17T07:50:29 Z |
web |
Dreaming (IOI13_dreaming) |
C++17 |
|
1000 ms |
20356 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 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
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)
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
20356 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 |
308 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
312 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
308 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
308 KB |
Output is correct |
| 24 |
Correct |
1 ms |
304 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
20356 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
11612 KB |
Output isn't correct |
| 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 |
308 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
312 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
308 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
308 KB |
Output is correct |
| 24 |
Correct |
1 ms |
304 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
2 ms |
444 KB |
Output is correct |
| 27 |
Correct |
3 ms |
596 KB |
Output is correct |
| 28 |
Correct |
4 ms |
724 KB |
Output is correct |
| 29 |
Correct |
2 ms |
468 KB |
Output is correct |
| 30 |
Correct |
4 ms |
596 KB |
Output is correct |
| 31 |
Correct |
4 ms |
756 KB |
Output is correct |
| 32 |
Correct |
2 ms |
468 KB |
Output is correct |
| 33 |
Incorrect |
4 ms |
572 KB |
Output isn't correct |
| 34 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
20356 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
