Submission #31747

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
31747	2017-09-05T19:26:51 Z	hyperioi	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	1326 ms	238292 KB

// #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

// #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.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	6180 KB	Output is correct
2	Correct	6 ms	8028 KB	Output is correct
3	Correct	19 ms	11724 KB	Output is correct
4	Correct	3 ms	6972 KB	Output is correct
5	Correct	6 ms	7236 KB	Output is correct
6	Correct	9 ms	8556 KB	Output is correct
7	Correct	26 ms	11724 KB	Output is correct
8	Correct	12 ms	11196 KB	Output is correct
9	Correct	15 ms	10932 KB	Output is correct
10	Correct	9 ms	8028 KB	Output is correct
11	Correct	12 ms	8556 KB	Output is correct
12	Correct	0 ms	5916 KB	Output is correct
13	Correct	22 ms	11724 KB	Output is correct
14	Correct	26 ms	11724 KB	Output is correct
15	Correct	28 ms	11460 KB	Output is correct
16	Correct	26 ms	11460 KB	Output is correct
17	Correct	26 ms	11460 KB	Output is correct
18	Correct	22 ms	11460 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1214 ms	238276 KB	Output is correct
2	Correct	1302 ms	238284 KB	Output is correct
3	Correct	1269 ms	238292 KB	Output is correct
4	Correct	1122 ms	236428 KB	Output is correct
5	Correct	1214 ms	236428 KB	Output is correct
6	Correct	1214 ms	236428 KB	Output is correct
7	Correct	1225 ms	236428 KB	Output is correct
8	Correct	1198 ms	236428 KB	Output is correct
9	Correct	1185 ms	236428 KB	Output is correct
10	Correct	842 ms	237092 KB	Output is correct
11	Correct	849 ms	237092 KB	Output is correct
12	Correct	1162 ms	215212 KB	Output is correct
13	Correct	992 ms	215212 KB	Output is correct
14	Correct	1066 ms	225820 KB	Output is correct
15	Correct	1052 ms	236692 KB	Output is correct
16	Correct	1116 ms	236692 KB	Output is correct
17	Correct	1125 ms	236428 KB	Output is correct
18	Correct	1245 ms	236428 KB	Output is correct
19	Correct	1296 ms	236428 KB	Output is correct
20	Correct	779 ms	236428 KB	Output is correct
21	Correct	738 ms	232988 KB	Output is correct
22	Correct	1179 ms	236428 KB	Output is correct
23	Correct	1142 ms	236428 KB	Output is correct
24	Correct	1115 ms	236428 KB	Output is correct
25	Correct	1105 ms	236428 KB	Output is correct
26	Correct	1178 ms	236428 KB	Output is correct
27	Correct	1178 ms	236428 KB	Output is correct
28	Correct	1242 ms	236428 KB	Output is correct
29	Correct	1115 ms	215212 KB	Output is correct
30	Correct	1138 ms	224756 KB	Output is correct
31	Correct	6 ms	8028 KB	Output is correct
32	Correct	9 ms	8556 KB	Output is correct
33	Correct	19 ms	11196 KB	Output is correct
34	Correct	12 ms	8028 KB	Output is correct
35	Correct	6 ms	6972 KB	Output is correct
36	Correct	3 ms	6444 KB	Output is correct
37	Correct	0 ms	6180 KB	Output is correct
38	Correct	0 ms	6180 KB	Output is correct
39	Correct	0 ms	5916 KB	Output is correct
40	Correct	3 ms	6708 KB	Output is correct
41	Correct	6 ms	6972 KB	Output is correct
42	Correct	0 ms	6180 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	6972 KB	Output is correct
2	Correct	3 ms	6972 KB	Output is correct
3	Correct	6 ms	6972 KB	Output is correct
4	Correct	114 ms	41916 KB	Output is correct
5	Correct	146 ms	41916 KB	Output is correct
6	Correct	145 ms	41916 KB	Output is correct
7	Correct	132 ms	41916 KB	Output is correct
8	Correct	122 ms	41916 KB	Output is correct
9	Correct	725 ms	233516 KB	Output is correct
10	Correct	706 ms	233516 KB	Output is correct
11	Correct	766 ms	233516 KB	Output is correct
12	Correct	0 ms	6180 KB	Output is correct
13	Correct	0 ms	6444 KB	Output is correct
14	Correct	0 ms	5916 KB	Output is correct
15	Correct	0 ms	5916 KB	Output is correct

Subtask #4
55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1192 ms	238276 KB	Output is correct
2	Correct	1182 ms	238276 KB	Output is correct
3	Correct	1326 ms	238276 KB	Output is correct
4	Correct	1138 ms	236428 KB	Output is correct
5	Correct	1238 ms	236428 KB	Output is correct
6	Correct	1156 ms	236428 KB	Output is correct
7	Correct	1245 ms	236428 KB	Output is correct
8	Correct	1154 ms	236428 KB	Output is correct
9	Correct	1222 ms	236428 KB	Output is correct
10	Correct	835 ms	237092 KB	Output is correct
11	Correct	794 ms	237092 KB	Output is correct
12	Correct	1145 ms	215212 KB	Output is correct
13	Correct	1042 ms	215212 KB	Output is correct
14	Correct	1132 ms	225820 KB	Output is correct
15	Correct	1079 ms	236692 KB	Output is correct
16	Correct	1169 ms	236692 KB	Output is correct
17	Correct	1132 ms	236428 KB	Output is correct
18	Correct	1202 ms	236428 KB	Output is correct
19	Correct	1249 ms	236428 KB	Output is correct
20	Correct	739 ms	236428 KB	Output is correct
21	Correct	794 ms	232988 KB	Output is correct
22	Correct	1225 ms	236428 KB	Output is correct
23	Correct	1192 ms	236428 KB	Output is correct
24	Correct	1182 ms	236428 KB	Output is correct
25	Correct	1178 ms	236428 KB	Output is correct
26	Correct	1125 ms	236428 KB	Output is correct
27	Correct	1242 ms	236428 KB	Output is correct
28	Correct	1268 ms	236428 KB	Output is correct
29	Correct	1132 ms	215212 KB	Output is correct
30	Correct	1062 ms	224756 KB	Output is correct

Subtask #5
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1249 ms	238276 KB	Output is correct
2	Correct	1169 ms	238276 KB	Output is correct
3	Correct	1192 ms	238276 KB	Output is correct
4	Correct	1202 ms	236428 KB	Output is correct
5	Correct	1202 ms	236428 KB	Output is correct
6	Correct	1192 ms	236428 KB	Output is correct
7	Correct	1162 ms	236428 KB	Output is correct
8	Correct	1142 ms	236428 KB	Output is correct
9	Correct	1212 ms	236428 KB	Output is correct
10	Correct	897 ms	237092 KB	Output is correct
11	Correct	872 ms	237092 KB	Output is correct
12	Correct	1079 ms	215212 KB	Output is correct
13	Correct	1004 ms	215212 KB	Output is correct
14	Correct	1112 ms	225820 KB	Output is correct
15	Correct	1194 ms	236164 KB	Output is correct
16	Correct	1109 ms	236692 KB	Output is correct
17	Correct	1142 ms	236428 KB	Output is correct
18	Correct	1238 ms	236428 KB	Output is correct
19	Correct	1142 ms	236428 KB	Output is correct
20	Correct	679 ms	236428 KB	Output is correct
21	Correct	728 ms	232988 KB	Output is correct
22	Correct	1194 ms	236428 KB	Output is correct
23	Correct	1154 ms	236428 KB	Output is correct
24	Correct	1242 ms	236428 KB	Output is correct
25	Correct	1198 ms	236428 KB	Output is correct
26	Correct	1269 ms	236428 KB	Output is correct
27	Correct	1292 ms	236428 KB	Output is correct
28	Correct	1252 ms	236436 KB	Output is correct
29	Correct	1126 ms	215212 KB	Output is correct
30	Correct	1088 ms	224756 KB	Output is correct
31	Correct	9 ms	8028 KB	Output is correct
32	Correct	12 ms	8556 KB	Output is correct
33	Correct	15 ms	11196 KB	Output is correct
34	Correct	6 ms	8028 KB	Output is correct
35	Correct	6 ms	6972 KB	Output is correct
36	Correct	0 ms	6444 KB	Output is correct
37	Correct	0 ms	6180 KB	Output is correct
38	Correct	0 ms	6180 KB	Output is correct
39	Correct	0 ms	5916 KB	Output is correct
40	Correct	6 ms	6708 KB	Output is correct
41	Correct	6 ms	6972 KB	Output is correct
42	Correct	0 ms	6180 KB	Output is correct

Submission #31747

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 55.0 / 55.0

Subtask #5 17.0 / 17.0

Subtask #1
8.0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
55.0 / 55.0

Subtask #5
17.0 / 17.0