/*************************************************************************
* *
* XX Olimpiada Informatyczna *
* *
* Zadanie: Multidrink *
* Autor: Przemyslaw Horban *
* Zlozonosc czasowa: O(n!) *
* Opis: Rozwiazanie powolne, wczytujemy drzewo i *
* generujemy permutacje, sprawdzajac, czy *
* stanowi ona szukana sciezke *
* *
*************************************************************************/
#include<iostream>
#include<set>
#include<iomanip>
#include<sstream>
#include<fstream>
#include<stack>
#include<cstdio>
#include<cmath>
#include<cassert>
#include<queue>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<cstring>
#include<cctype>
using namespace std;
#define fe(e,C) for(__typeof((C).begin()) e = (C).begin(); e != (C).end(); e++)
#define fi(i,n) for(int (i) = 0, __end = (n); (i) < __end; i++)
#define iterate_until(i,s,n) for(int (i) = (s), __end = (n); (i) < __end; i++)
#define iterate_to(i,a,b) ft(i,a,b)
#define ft(i,a,b) for(int (i) = (a), __end = (b); (i) <= __end; (i)++)
#define fd(i,a,b) for(int (i) = (a), __end = (b); (i) >= __end; (i)--)
#define fs(i,C) fi(i,SZ(C))
#define ALL(V) (V).begin(), (V).end()
#define SET(T, c) memset(T, c, sizeof(T))
// Przemyslaw Horban ([email protected])
//
// This code is shared among solutions and verifiers
#define fe(e,C) for(__typeof((C).begin()) e = (C).begin(); e != (C).end(); e++)
#define foreach(VAR_DEF, C) \
fe(__varname, C) \
for(bool run_once = true; run_once; ) \
for(VAR_DEF = *(__varname); run_once; run_once = false)
#ifndef DEBUG
#define DEBUG 0
#endif
class Graph {
protected:
int minNode, _edgeCount;
vector<vector<int> > E;
public:
Graph(int smallestNode, int largestNode) {
minNode = smallestNode;
int size = largestNode - (smallestNode - 1);
E.clear();
E.resize(size);
_edgeCount = 0;
}
void addEdge(int u, int v) {
_edgeCount += 1;
u -= minNode;
v -= minNode;
E[u].push_back(v);
E[v].push_back(u);
}
size_t neighbourCount(int u) const {
return E[u - minNode].size();
}
vector<int> neighbours(int u) const {
vector<int> neighs(E[u - minNode]);
iterate_until(i, 0, neighs.size())
neighs[i] += minNode;
return neighs;
}
bool hasUnusedNeighbour(int u, const vector<bool> used) const {
assert(nodeCount() + minNode - 1 < used.size());
u -= minNode;
foreach(int v, E[u]) {
v += minNode;
if(!used[v])
return true;
}
return false;
}
size_t nodeCount() const {
return E.size();
}
size_t edgeCount() const {
return _edgeCount;
}
bool isConnected() const {
vector<bool> onFringe(nodeCount(), false);
vector<int> fringeNodes;
fringeNodes.push_back(0);
onFringe[0] = true;
while(!fringeNodes.empty()) {
int u = fringeNodes.back();
fringeNodes.pop_back();
fe(nextIt, E[u]) {
int v = *nextIt;
if(!onFringe[v]) {
fringeNodes.push_back(v);
onFringe[v] = true;
}
}
}
return count(ALL(onFringe), false) == 0;
}
};
class TwoStepNeighIterator;
class Tree: public Graph {
friend class TwoStepNeighIterator;
public:
Tree(FILE *input, int numerationStart): Graph(numerationStart,
read_int(input)) {
while(edgeCount() < nodeCount() - 1)
addEdge(read_int(input), read_int(input));
buildFatherSonRelation();
}
// Haha! It takes O(1) time.
bool areDistantByAtMost2(int u, int v, int *middleMan=NULL) const {
u -= minNode;
v -= minNode;
if(middleMan) *middleMan = -1;
// By definition they may be distant by 0
if(u == v)
return true;
// Directly connected
if(father[u] == v || father[v] == u)
return true;
// Distant by two edges
// v
// /
// m
// /
// u
if(father[father[u]] == v) {
if(middleMan) *middleMan = father[u] + minNode;
return true;
}
// u
// /
// m
// /
// v
if(father[father[v]] == u) {
if(middleMan) *middleMan = father[v] + minNode;
return true;
}
// m
// / |
// u v
if(father[u] == father[v]) {
if(middleMan) *middleMan = father[u] + minNode;
return true;
}
return false;
}
bool fatherAndSon(int fatherNd, int childNd) const {
childNd -= minNode;
fatherNd -= minNode;
return father[childNd] == fatherNd;
}
bool areNeighbours(int u, int v) const {
u -= minNode;
v -= minNode;
// Directly connected
return father[u] == v || father[v] == u;
}
private:
vector<int> father;
void buildFatherSonRelation() {
father.clear();
father.resize(nodeCount());
vector<bool> onFringe(nodeCount(), false);
vector<int> fringeNodes;
fringeNodes.push_back(0);
onFringe[0] = true;
father[0] = 0;
while(!fringeNodes.empty()) {
int u = fringeNodes.back();
fringeNodes.pop_back();
fe(nextIt, E[u]) {
int v = *nextIt;
// This is a Tree - if it's on fringe,
// than it must be the father
if(!onFringe[v]) {
// u adopts v
father[v] = u;
fringeNodes.push_back(v);
onFringe[v] = true;
}
}
}
}
static int read_int(FILE *input) {
int t;
int result = fscanf(input, "%d", &t);
assert(result == 1);
return t;
}
};
class TwoStepNeighIterator {
const Tree *gPtr;
int u;
vector<int>::const_iterator nodesToGoIt, nodesToGoEnd;
vector<int>::const_iterator neighbourIt, neighboursEnd;
public:
TwoStepNeighIterator(const Tree *gPtr, int u): gPtr(gPtr), u(u) {
const Tree &g = *gPtr;
int root = u - g.minNode;;
neighbourIt = g.E[root].begin();
neighboursEnd = g.E[root].end();
nodesToGoIt = g.E[root].begin();
nodesToGoEnd = g.E[root].end();
}
int next() {
if(neighbourIt != neighboursEnd) {
int v = *neighbourIt + gPtr->minNode;
neighbourIt++;
if(v == u)
return next();
else
return v;
}
else if(nodesToGoIt != nodesToGoEnd) {
neighbourIt = gPtr->E[*nodesToGoIt].begin();
neighboursEnd = gPtr->E[*nodesToGoIt].end();
nodesToGoIt++;
return next();
}
else
return -1;
}
};
// Iterative brutal path search
//
// CutoffMem is the datatype that cutOff function
// can use to memorize which cases have already been
// explored and make a cutoff decision based on that.
template<typename CutoffMem = char>
class PathSearch {
const Tree &g;
vector<int> p;
vector<bool> used;
vector<TwoStepNeighIterator> iters;
vector<CutoffMem> cutoffMem;
public:
PathSearch(const Tree &g): g(g) {}
// Returns a vector with solution or empty vector if not found.
vector<int> findTwoStepPath() {
vector<int> solution;
p.clear();
p.push_back(1);
used.clear();
used.resize(g.nodeCount()+1, false);
used[1] = true;
if(DEBUG) {
iterate_to(u, 1, g.nodeCount()) {
TwoStepNeighIterator it(&g, u);
printf("Sasiedzi %d: ", u);
while(true) {
int v = it.next();
if(v == -1) break;
printf("%d ", v);
}
printf("\n");
}
}
search_step();
if(p.size() == g.nodeCount())
solution.swap(p);
return solution;
}
virtual ~PathSearch() {}
protected:
virtual bool cutOff(const Tree &g,
int preLast, int last,
const vector<bool> &used,
CutoffMem *cutoffMemPtr) = 0;
private:
void search_step() {
fake_recurse:
if(p.size() == g.nodeCount() && p.back() == (int)g.nodeCount()) {
// Solution found. Real return.
return;
}
iters.push_back(TwoStepNeighIterator(&g, p.back()));
p.push_back(-1);
cutoffMem.push_back(CutoffMem());
while(true) {
p.back() = iters.back().next();
if(p.back() == -1)
break;
if(DEBUG) {
foreach(int u, p)
printf("%d ", u);
printf("\n");
}
if(!used[p.back()]) {
used[p.back()] = true;
// Jestem w p[-1], ostatni byl p[-2], uzyte sa used, a
// a drzewo jest g.
if(!cutOff(g, *(p.end()-2), *(p.end()-1), used, &*(cutoffMem.end()-1)))
goto fake_recurse; // search_step() - simulated recursive call
fake_return:
// end of search_step() fake call
used[p.back()] = false;
}
}
p.pop_back();
iters.pop_back();
cutoffMem.pop_back();
if(iters.empty()) // Real return - no solution found.
return;
else // return to callpoint in the while
goto fake_return;
}
};
int main() {
Tree g(stdin, 1);
vector<int> P;
iterate_to(i, 1, g.nodeCount())
P.push_back(i);
do {
bool isValidPath = true;
iterate_until(i, 0, g.nodeCount() - 1) {
if(!g.areDistantByAtMost2(P[i], P[i+1])) {
isValidPath = false;
break;
}
}
if(isValidPath) {
fe(nodeIt, P)
printf("%d\n", *nodeIt);
return 0;
}
} while(next_permutation(P.begin() + 1, P.end() - 1));
puts("BRAK");
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 4 |
Correct |
4883 ms |
2024 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 3 |
Correct |
2383 ms |
2024 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 3 |
Correct |
146 ms |
2024 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
2024 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 6 |
Correct |
386 ms |
2024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2024 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
2024 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 3 |
Execution timed out |
12000 ms |
2024 KB |
Execution timed out |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
2024 KB |
Execution timed out |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
2024 KB |
Execution timed out |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
2024 KB |
Execution timed out |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
2024 KB |
Execution timed out |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
2024 KB |
Execution timed out |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
2024 KB |
Execution timed out |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
2024 KB |
Execution timed out |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
2348 KB |
Execution timed out |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
2348 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
8812 KB |
Execution timed out |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
9248 KB |
Execution timed out |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
8848 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
36528 KB |
Execution timed out |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
36528 KB |
Execution timed out |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
34824 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
12000 ms |
34796 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
