Submission #31747

#	Time	Username	Problem	Language	Result	Execution time	Memory
31747		hyperioi	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	1326 ms	238292 KiB

Joi

// #include "Joi.h"
void Joi(int N, int M, int A[], int B[], long long X, int T);
void MessageBoard(int attr, int msg);

// #include "Ioi.h"
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T);
int Move(int dest);

#include <vector>
#include <set>
#include <map>
#include <cstdio>
#include <cassert>

#define XMAX     60
#define NMAX     10000
#define MMAX     20000
#define MOVEMAX  20000

#define NDEBUG

using namespace std;

// ############################################################################################################
class Node {
public:
    set<int>  edges;
    Node();
    void add_edge(int neighbor);
    bool is_leaf();
};

// ############################################################################################################
class Graph {
private:
    typedef map<int, Node>  nodes_t;
    nodes_t  nodes;
public:
    Graph();
    Graph(int N, int M, int A[], int B[]);
    Graph(const Graph &T, bool allow_cycles = true, int max_size = -1);
    Node &  operator[] (int id);
    void    add_node(int id, int from = -1);                         // from = -1 means no from
    void    build_subgraph_coverage(int size);
    bool    has_node(int id);
    void    remove_node(int id);
    size_t  size();
    int     trim(int protected_id);                                  // Trim a leaf node (but not protected_id)
};

// ############################################################################################################
class Attraction {
public:
    Graph  subgraph;
    int    index;
    Attraction();
    bool has_index();
};

static vector<Attraction>  Park;

// ############################################################################################################
class Bits {
private:
    int  x[XMAX];
public:
    Bits(long long X);
    long long get();
    int       get_bit(int index);
    void      set_bit(int index, int bit);
};

// ############################################################################################################
// class Node
// ############################################################################################################

// ############################################################################################################
Node::Node()
    : edges()
{}

// ############################################################################################################
void Node::add_edge(int neighbor)
{
    edges.insert(neighbor);
}

// ############################################################################################################
bool Node::is_leaf()
{
    return edges.size() <= 1;
}

// ############################################################################################################
// class Graph
// ############################################################################################################

// ############################################################################################################
Graph::Graph()
    : nodes()
{}

// ############################################################################################################
Graph::Graph(int N, int M, int A[], int B[])
    : nodes()
{
    for ( int i = 0; i < M; ++i ) {
        nodes[A[i]].add_edge(B[i]);                                  // This will create nodes[A[i]] if necessary
        nodes[B[i]].add_edge(A[i]);                                  // ... idem for nodes[B[i]]
    }
}

// ############################################################################################################
Graph::Graph(const Graph &T, bool allow_cycles, int max_size)
    : nodes()
{
    vector<int>  pending = { T.nodes.begin()->first };               // List of nodes pending processing
    set<int>     done;

    add_node(pending[0]);                                            // All pending nodes are added already

    while ( pending.size() > 0 ) {
        int  current = pending.back();
        pending.pop_back();
        done.insert(current);
        for ( auto &&neighbor: T.nodes.at(current).edges ) {
            if ( (max_size >= 0) && ((int)size() >= max_size) ) {
                return;
            }
            if ( done.count(neighbor) ) {
                continue;
            }
            if ( allow_cycles || !has_node(neighbor) ) {
                add_node(neighbor, current);
                pending.push_back(neighbor);
            }
        }
    }
}

// ############################################################################################################
Node & Graph::operator[] (int id)
{
    return nodes[id];
}

// ############################################################################################################
void Graph::add_node(int id, int from)
{
    if ( !has_node(id) ) {
        nodes[id] = Node();
    }

    if ( from >= 0 ) {
        nodes[id].add_edge(from);
        nodes[from].add_edge(id);
    }
}

// ############################################################################################################
void Graph::build_subgraph_coverage(int size)
{
    Graph        S     = Graph(*this, false, size);

    int          index = 0;

    vector<int>  pending;                                            // List of nodes whose neighbors must be processed

    for ( auto &&node : S.nodes ) {
        int  id = node.first;
        Park[id].index    = index;
        Park[id].subgraph = S;
#if !defined(NDEBUG)
        printf("Park[%d].index = %d\n",id,index);
#endif
        pending.push_back(id);
        index++;
    }

    while ( pending.size() > 0 ) {
        int  current = pending.back();
        pending.pop_back();
        for ( auto &&neighbor: nodes.at(current).edges ) {
            if ( Park[neighbor].has_index() ) {
                continue;                                            // Ignore nodes that we processed already (no infinite loop)
            }
            Graph  S     = Park[current].subgraph;
            int    index = Park[S.trim(current)].index;
            assert(index<XMAX);
            S.add_node(neighbor, current);
            Park[neighbor].index    = index;
            Park[neighbor].subgraph = S;
#if !defined(NDEBUG)
            printf("Park[%d].index = %d\n",neighbor,index);
#endif
            pending.push_back(neighbor);
        }
    }
}

// ############################################################################################################
bool Graph::has_node(int id)
{
    return nodes.count(id) > 0;
}

// ############################################################################################################
void Graph::remove_node(int id)
{
    for ( auto &&neighbor: nodes[id].edges ) {
        nodes[neighbor].edges.erase(id);
    }
    nodes.erase(id);
}

// ############################################################################################################
size_t Graph::size()
{
    return nodes.size();
}

// ############################################################################################################
// Trim a leaf node (but not protected_id). Return id of trimmed node.
int Graph::trim(int protected_id)
{
    for ( auto &&node: nodes ) {
        int  id = node.first;
        if ( (id != protected_id) && node.second.is_leaf() ) {
            remove_node(id);
            return id;
        }
    }
    throw std::runtime_error("no unprotected leaf found.");
}

// ############################################################################################################
// class Attraction
// ############################################################################################################

// ############################################################################################################
Attraction::Attraction()
    : subgraph(), index(-1)
{}

// ############################################################################################################
bool Attraction::has_index()
{
    return index >= 0;
}

// ############################################################################################################
// class Bits
// ############################################################################################################

// ############################################################################################################
Bits::Bits(long long X)
{
    for ( int i = 0; i < XMAX; i++ ) {
        this->x[i] = X & 1;
        X        >>= 1;
    }
}

// ############################################################################################################
long long Bits::get()
{
    long long  X = 0;

    for ( int i = XMAX - 1; i >= 0; i-- ) {
        X <<= 1;
        X  |= x[i];
    }
    return X;
}

// ############################################################################################################
int Bits::get_bit(int index)
{
    return x[index];
}

// ############################################################################################################
void Bits::set_bit(int index, int bit)
{
    x[index] = bit;
}

// ############################################################################################################
// Joi
// ############################################################################################################

#if defined(JOIGRADER)
// ############################################################################################################
void Joi(int N, int M, int A[], int B[], long long X, int T)
{
    Bits   XB(X);                                                    // Convert 60-bit X into an array of bits
    Graph  G(N, M, A, B);
    Graph  ST(G, false);                                             // ST = graph spanning tree (no cycles)

#if !defined(NDEBUG)
    printf("Joi(N=%d,M=%d)\n",N,M);
#endif
    Park.resize(N);
    ST.build_subgraph_coverage(XMAX);                                // Cover the spanning tree with subtrees of size XMAX

    for ( int id = 0; id < (int)Park.size(); ++id ) {
#if !defined(NDEBUG)
        printf("[id=%3d,index=%2d] = %d\n", id, Park[id].index, XB.get_bit(Park[id].index));
#endif
        MessageBoard( id, XB.get_bit(Park[id].index) );
    }
}
#endif

// ############################################################################################################
// Ioi
// ############################################################################################################

#if defined(IOIGRADER)
// ############################################################################################################
void IoiVisit(Graph &S, int parent, int msg, Bits &XB, set<int> &visited)
{
    XB.set_bit(Park[parent].index, msg);
    visited.insert(parent);
    for ( auto &&child : S[parent].edges ) {
        if ( visited.count(child) > 0 ) {
            continue;                                                // Ignore parent
        }
        int  childMsg = Move(child);
        IoiVisit(S, child, childMsg, XB, visited);
        Move(parent);
    }
}

// ############################################################################################################
// P = current node id, V = msg of current node
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
    Bits      XB(0);                                                 // This will contain our 60-bit X (as an array of bits)
    Graph     G(N, M, A, B);
    Graph     ST(G, false);                                          // ST = graph spanning tree (no cycles)

    Park.resize(N);
    ST.build_subgraph_coverage(XMAX);                                // Cover the spanning tree with subtrees of size XMAX

    Graph     S = Park[P].subgraph;
    set<int>  visited;
    IoiVisit(S, P, V, XB, visited);

    return XB.get();
}
#endif

Ioi

// #include "Joi.h"
void Joi(int N, int M, int A[], int B[], long long X, int T);
void MessageBoard(int attr, int msg);

// #include "Ioi.h"
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T);
int Move(int dest);

#include <vector>
#include <set>
#include <map>
#include <cstdio>
#include <cassert>

#define XMAX     60
#define NMAX     10000
#define MMAX     20000
#define MOVEMAX  20000

#define NDEBUG

using namespace std;

// ############################################################################################################
class Node {
public:
    set<int>  edges;
    Node();
    void add_edge(int neighbor);
    bool is_leaf();
};

// ############################################################################################################
class Graph {
private:
    typedef map<int, Node>  nodes_t;
    nodes_t  nodes;
public:
    Graph();
    Graph(int N, int M, int A[], int B[]);
    Graph(const Graph &T, bool allow_cycles = true, int max_size = -1);
    Node &  operator[] (int id);
    void    add_node(int id, int from = -1);                         // from = -1 means no from
    void    build_subgraph_coverage(int size);
    bool    has_node(int id);
    void    remove_node(int id);
    size_t  size();
    int     trim(int protected_id);                                  // Trim a leaf node (but not protected_id)
};

// ############################################################################################################
class Attraction {
public:
    Graph  subgraph;
    int    index;
    Attraction();
    bool has_index();
};

static vector<Attraction>  Park;

// ############################################################################################################
class Bits {
private:
    int  x[XMAX];
public:
    Bits(long long X);
    long long get();
    int       get_bit(int index);
    void      set_bit(int index, int bit);
};

// ############################################################################################################
// class Node
// ############################################################################################################

// ############################################################################################################
Node::Node()
    : edges()
{}

// ############################################################################################################
void Node::add_edge(int neighbor)
{
    edges.insert(neighbor);
}

// ############################################################################################################
bool Node::is_leaf()
{
    return edges.size() <= 1;
}

// ############################################################################################################
// class Graph
// ############################################################################################################

// ############################################################################################################
Graph::Graph()
    : nodes()
{}

// ############################################################################################################
Graph::Graph(int N, int M, int A[], int B[])
    : nodes()
{
    for ( int i = 0; i < M; ++i ) {
        nodes[A[i]].add_edge(B[i]);                                  // This will create nodes[A[i]] if necessary
        nodes[B[i]].add_edge(A[i]);                                  // ... idem for nodes[B[i]]
    }
}

// ############################################################################################################
Graph::Graph(const Graph &T, bool allow_cycles, int max_size)
    : nodes()
{
    vector<int>  pending = { T.nodes.begin()->first };               // List of nodes pending processing
    set<int>     done;

    add_node(pending[0]);                                            // All pending nodes are added already

    while ( pending.size() > 0 ) {
        int  current = pending.back();
        pending.pop_back();
        done.insert(current);
        for ( auto &&neighbor: T.nodes.at(current).edges ) {
            if ( (max_size >= 0) && ((int)size() >= max_size) ) {
                return;
            }
            if ( done.count(neighbor) ) {
                continue;
            }
            if ( allow_cycles || !has_node(neighbor) ) {
                add_node(neighbor, current);
                pending.push_back(neighbor);
            }
        }
    }
}

// ############################################################################################################
Node & Graph::operator[] (int id)
{
    return nodes[id];
}

// ############################################################################################################
void Graph::add_node(int id, int from)
{
    if ( !has_node(id) ) {
        nodes[id] = Node();
    }

    if ( from >= 0 ) {
        nodes[id].add_edge(from);
        nodes[from].add_edge(id);
    }
}

// ############################################################################################################
void Graph::build_subgraph_coverage(int size)
{
    Graph        S     = Graph(*this, false, size);

    int          index = 0;

    vector<int>  pending;                                            // List of nodes whose neighbors must be processed

    for ( auto &&node : S.nodes ) {
        int  id = node.first;
        Park[id].index    = index;
        Park[id].subgraph = S;
#if !defined(NDEBUG)
        printf("Park[%d].index = %d\n",id,index);
#endif
        pending.push_back(id);
        index++;
    }

    while ( pending.size() > 0 ) {
        int  current = pending.back();
        pending.pop_back();
        for ( auto &&neighbor: nodes.at(current).edges ) {
            if ( Park[neighbor].has_index() ) {
                continue;                                            // Ignore nodes that we processed already (no infinite loop)
            }
            Graph  S     = Park[current].subgraph;
            int    index = Park[S.trim(current)].index;
            assert(index<XMAX);
            S.add_node(neighbor, current);
            Park[neighbor].index    = index;
            Park[neighbor].subgraph = S;
#if !defined(NDEBUG)
            printf("Park[%d].index = %d\n",neighbor,index);
#endif
            pending.push_back(neighbor);
        }
    }
}

// ############################################################################################################
bool Graph::has_node(int id)
{
    return nodes.count(id) > 0;
}

// ############################################################################################################
void Graph::remove_node(int id)
{
    for ( auto &&neighbor: nodes[id].edges ) {
        nodes[neighbor].edges.erase(id);
    }
    nodes.erase(id);
}

// ############################################################################################################
size_t Graph::size()
{
    return nodes.size();
}

// ############################################################################################################
// Trim a leaf node (but not protected_id). Return id of trimmed node.
int Graph::trim(int protected_id)
{
    for ( auto &&node: nodes ) {
        int  id = node.first;
        if ( (id != protected_id) && node.second.is_leaf() ) {
            remove_node(id);
            return id;
        }
    }
    throw std::runtime_error("no unprotected leaf found.");
}

// ############################################################################################################
// class Attraction
// ############################################################################################################

// ############################################################################################################
Attraction::Attraction()
    : subgraph(), index(-1)
{}

// ############################################################################################################
bool Attraction::has_index()
{
    return index >= 0;
}

// ############################################################################################################
// class Bits
// ############################################################################################################

// ############################################################################################################
Bits::Bits(long long X)
{
    for ( int i = 0; i < XMAX; i++ ) {
        this->x[i] = X & 1;
        X        >>= 1;
    }
}

// ############################################################################################################
long long Bits::get()
{
    long long  X = 0;

    for ( int i = XMAX - 1; i >= 0; i-- ) {
        X <<= 1;
        X  |= x[i];
    }
    return X;
}

// ############################################################################################################
int Bits::get_bit(int index)
{
    return x[index];
}

// ############################################################################################################
void Bits::set_bit(int index, int bit)
{
    x[index] = bit;
}

// ############################################################################################################
// Joi
// ############################################################################################################

#if defined(JOIGRADER)
// ############################################################################################################
void Joi(int N, int M, int A[], int B[], long long X, int T)
{
    Bits   XB(X);                                                    // Convert 60-bit X into an array of bits
    Graph  G(N, M, A, B);
    Graph  ST(G, false);                                             // ST = graph spanning tree (no cycles)

#if !defined(NDEBUG)
    printf("Joi(N=%d,M=%d)\n",N,M);
#endif
    Park.resize(N);
    ST.build_subgraph_coverage(XMAX);                                // Cover the spanning tree with subtrees of size XMAX

    for ( int id = 0; id < (int)Park.size(); ++id ) {
#if !defined(NDEBUG)
        printf("[id=%3d,index=%2d] = %d\n", id, Park[id].index, XB.get_bit(Park[id].index));
#endif
        MessageBoard( id, XB.get_bit(Park[id].index) );
    }
}
#endif

// ############################################################################################################
// Ioi
// ############################################################################################################

#if defined(IOIGRADER)
// ############################################################################################################
void IoiVisit(Graph &S, int parent, int msg, Bits &XB, set<int> &visited)
{
    XB.set_bit(Park[parent].index, msg);
    visited.insert(parent);
    for ( auto &&child : S[parent].edges ) {
        if ( visited.count(child) > 0 ) {
            continue;                                                // Ignore parent
        }
        int  childMsg = Move(child);
        IoiVisit(S, child, childMsg, XB, visited);
        Move(parent);
    }
}

// ############################################################################################################
// P = current node id, V = msg of current node
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
    Bits      XB(0);                                                 // This will contain our 60-bit X (as an array of bits)
    Graph     G(N, M, A, B);
    Graph     ST(G, false);                                          // ST = graph spanning tree (no cycles)

    Park.resize(N);
    ST.build_subgraph_coverage(XMAX);                                // Cover the spanning tree with subtrees of size XMAX

    Graph     S = Park[P].subgraph;
    set<int>  visited;
    IoiVisit(S, P, V, XB, visited);

    return XB.get();
}
#endif

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17