oj.uz

답안 #198111

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198111 2020-01-24T18:12:50 Z model_code Dynamic Diameter (CEOI19_diameter) C++17
49 / 100
 5000 ms 162020 KB 
#include <vector>
#include <stack>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <iomanip>
#include <set>
#include <functional>
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;

#define x first
#define y second
typedef std::pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<ui, ui> puu;

template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;

ui logceil(ll x) { return x ? 8 * sizeof(ll) - __builtin_clzll(x) : 0; }

namespace std {
template<typename T, typename U>struct hash<pair<T, U>> {
        hash<T>t;
        hash<U>u;
        size_t operator()(const pair<T, U>&p)const {
                return t(p.x) ^ (u(p.y) << 7);
        }
};
}


template <typename EdgeType>
class DFSOrder {
public:
        DFSOrder(const vector<vector<EdgeType>> &_E) : T(0), N(_E.size()), E(_E), RevEnter(N), Enter(N), Exit(N) {
                dfs(0, -1);
        }

        vector<vector<EdgeType>> linearize() {
                vector<vector<EdgeType>> F(N);
                for (int i = 0; i < N; ++i) {
                        for (auto v : E[i]) {
                                F[conv(i)].push_back(conv(v));
                        }
                }
                return F;
        }

        void dfs(int u, int p) {
                RevEnter[T] = u;
                Enter[u] = T++;
                for (auto v : E[u]) if (t(v) != p) dfs(t(v), u);
                Exit[u] = T;
        }

        inline int t(const int&e) const {
                return e;
        }
        template <typename U> inline int t(const pair<int, U>&e) const {
                return e.x;
        }

        inline int conv(const int&e) const {
                return Enter[e];
        }
        template <typename U> inline pair<int, U> conv(const pair<int, U>&e) const {
                return {Enter[e.x], e.y};
        }

        const vector<int> &revEnter() const {
                return RevEnter;
        }
        const vector<int> &enter() const {
                return Enter;
        }
        const vector<int> &exit() const {
                return Exit;
        }

        int T, N;
        const vector<vector<EdgeType>> &E;
        vector<int> Enter, Exit, RevEnter;
};

/** Centroid decomposition.
 *
 * Input: graph as adjacency list (either int or pair<int,T>)
 * Output: array U of integers of size |V|
 *
 * Here, U[v] is the bfs order in the centroid tree. For DFS, only process
 * vertices with higher U[w] when processing centroid v, for instance:
 *
 * void dfs(int u, int p, int ctr, ...) {
 *      ....
 *      for (int v:E[u]) {
 *          if (v != p && U[v] > U[ctr]) {
 *              dfs(v, u, ctr, ...);
 *          }
 *      }
 * }
 */
template <typename EdgeType>
class CentroidDecomposition {
public:
        CentroidDecomposition(const vector<vector<EdgeType>> &E) : E(E) {}

        const vector<int>& findCentroids() {
                DFSOrder<EdgeType> DFS(E);
                auto EF = DFS.linearize();
                
                N = E.size();
                U.assign(N, -1);

                for (int j = 0; j < N; ) {
                        for (int i = N - 1; i >= 0; --i) {
                                if (U[i] >= 0) continue;

                                U[i] = -1;
                                bool root = true;
                                for (auto v : EF[i]) {
                                        if (U[t(v)] < 0) {
                                                if (t(v) > i) U[i] += U[t(v)];
                                                else root = false;
                                        }
                                }

                                if (root) {
                                        int n = -U[i], u = i, p = -1;
                                        while (true) {
                                                int s = n + U[u];
                                                for (auto v : EF[u]) if (t(v) != p && U[t(v)] < 0) s = max(s, -U[t(v)]);
                                                if (2 * s <= n) {
                                                        U[u] = j++;
                                                        break;
                                                } else {
                                                        for (auto v : EF[u]) if (t(v) != p && -U[t(v)] > n / 2) {
                                                                        p = u;
                                                                        u = t(v);
                                                                        break;
                                                                }
                                                }
                                        }
                                }
                        }
                }
                vector<int> Ans(N);
                for (int i = 0; i < N; ++i) Ans[i] = U[DFS.enter()[i]];
                swap(Ans, U);
                return U;
        }

        inline int t(const int&e) const {
                return e;
        }
        template <typename U> inline int t(const pair<int, U>&e) const {
                return e.x;
        }

        int N;
        const vector<vector<EdgeType>> &E;
        vector<int> U;
};

template<typename F>struct NoOp {
        void setup(ui, F) {} void op(F&p, F n, ui, ui) {
                p = n;
        } void down(F&, F&, F&, ui, ui) {}
};

template<typename F, typename SetOp, typename PowerOp>struct Lazy {
        void setup(ui s, F def) {
                this->def = def;
                this->s = s;
                L = new F[s]();
                fill(L, L + s, def);
        }
        void down(F&u, F&l, F&r, ui i, ui s) {
                op(l, L[i], i << 1, s>>1);
                op(r, L[i], i << 1 | 1, s >> 1);
                L[i] = def;
        }
        void op(F&p, F n, ui i, ui s) {
                p = sop(p, pop(n, s));
                if(i < this->s)this->L[i] = sop(this->L[i], n);
        }
        SetOp sop;
        PowerOp pop;
        F*L;
        ui s;
        F def;
};

template <typename F, typename CombineOp, typename ModifyOp = NoOp<F>> struct SegTree {
        void setup(ui s, F def) {
                n = 1 << logceil(s);
                T = vector<F>(2 * n, def);
                for (ui i = n - 1; i > 0; i--) T[i] = cop(T[i << 1], T[i << 1 | 1]);
                mop.setup(2 * n, def);
        }

        void setup(vector<F> & data, F def = F(), F def2 = F()) {
                n = 1 << logceil(data.size());
                T = vector<F>(2 * n, def);
                copy(data.begin(), data.end(), T.begin() + n);
                for (ui i = n - 1; i > 0; i--) T[i] = cop(T[i << 1], T[i << 1 | 1]);
                mop.setup(2 * n, def2);
        }

        inline void put(ui x, F n) {
                put(x, x, n);
        }
        inline void put(ui from, ui to, F v) {
                put2(from, to + 1, v, 1, n);
        }
        inline F get(ui x) {
                return get(x, x);
        }
        inline F get(ui from, ui to) {
                return get2(from, to + 1, 1, n);
        }

        void put2(ui from, ui to, F v, ui i, ui s) {
                if (from == 0 && to == s) {
                        mop.op(T[i], v, i, s);
                        return;
                }
                mop.down(T[i], T[i << 1], T[i << 1 | 1], i, s);
                s >>= 1;
                i <<= 1;
                if (to <= s) {
                        put2(from, to, v, i, s);
                } else if (from >= s) {
                        put2(from - s, to - s, v, i | 1, s);
                } else {
                        put2(from, s, v, i, s);
                        put2(0, to - s, v, i | 1, s);
                }
                T[i >> 1] = cop(T[i], T[i | 1]);
        }

        F get2(ui from, ui to, ui i, ui s) {
                while (true) {
                        if (from == 0 && to == s) return T[i];
                        mop.down(T[i], T[i << 1], T[i << 1 | 1], i, s);
                        s >>= 1;
                        i <<= 1;
                        if (to > s) {
                                to -= s;
                                if (from >= s) {
                                        from -= s;
                                        i |= 1;
                                } else return cop(get2(from, s, i, s), get2(0, to, i | 1, s));
                        }
                }
        }

        ui n;
        vector<F> T;
        CombineOp cop;
        ModifyOp mop;
};


template <typename F> struct AddOp {
        F operator()(F a, F b) {
                return a + b;
        }
};
template <typename F> struct MinOp {
        F operator()(F a, F b) {
                return std::min(a, b);
        }
};
template <typename F> struct MaxOp {
        F operator()(F a, F b) {
                return std::max(a, b);
        }
};
template <typename F> struct MultiplyOp {
        F operator()(F a, F b) {
                return a * b;
        }
};
template <typename F> struct MultOp {
        F operator()(F a, ui b) {
                return a * b;
        }
};
template <typename F> struct IdempOp {
        F operator()(F a, ui b) {
                return a;
        }
};
template <typename F> struct InverseOp {
        F operator()(F a, F b) {
                return b ? b - a : a;
        }
};

template<typename T> using AddSumTree = SegTree<T, AddOp<T>, Lazy<T, AddOp<T>, MultOp<T>>>;
template<typename T> using AddMaxTree = SegTree<T, MaxOp<T>, Lazy<T, AddOp<T>, IdempOp<T>>>;
template<typename T> using AddMinTree = SegTree<T, MinOp<T>, Lazy<T, AddOp<T>, IdempOp<T>>>;
template<typename T> using AssignMinTree = SegTree<T, MinOp<T>, Lazy<T, MinOp<T>, IdempOp<T>>>;
template<typename T> using AssignMaxTree = SegTree<T, MaxOp<T>, Lazy<T, MaxOp<T>, IdempOp<T>>>;
template<typename T> using XorTree = SegTree<T, AddOp<T>, Lazy<T, InverseOp<T>, MultOp<T>>>;

template<typename T> using SetMinTree = SegTree<T, MinOp<T>>;
template<typename T> using SetMaxTree = SegTree<T, MaxOp<T>>;
template<typename T> using SetMulTree = SegTree<T, MultiplyOp<T>>;


class Diameter {
public:
        // all edges (target, initial_cost)
        vector<vector<pair<int, ll>>> E;

        // level on which vertex is a centroid
        vector<int> Level;

        // (u,v) -> (centroid, root_edge_id),(left,right)
        // left-right is range of leaves (by dfs visit time) that hang below this edge
        // size of each vector is <= log N (by centroid decomposition)
        unordered_map<pii, vector<pair<pii, pii>>> EdgeToCtr;

        // for each centroid, the sum of root to leaf path, leaves ordered by dfs visit times
        // only used in the setup phase, then superseded by LeafDepths
        vector<vector<ll>> RootToLeafPath;

        // for each centroid the prefix sums of the subtrees hanging under edges adjacent to centroid
        vector<vector<int>> CentroidChildSubtreeSizes;

        // range add and range max; initialised by LeafDepths
        vector<AddMaxTree<ll>> LeafDepths;

        // per centroid, maximum root-to-leaf path for each edge adjacent to centroid
        vector<multiset<ll>> CtrMax;

        // per centroid, maximum cost path in that centroid
        multiset<ll> AllMax;

        void dfs(int u, int p, int ctr, int j, ll cost, int &T) {
                bool isLeaf = true;
                for (auto v : E[u]) {
                        if (v.x != p && Level[v.x] > Level[ctr]) {
                                isLeaf = false;
                                int begin = T;
                                dfs(v.x, u, ctr, j, cost + v.y, T);
                                int end = T;
                                EdgeToCtr[ {u, v.x}].push_back({{ctr, j}, {begin, end - 1}});
                                EdgeToCtr[ {v.x, u}].push_back({{ctr, j}, {begin, end - 1}});
                        }
                }

                if (isLeaf) {
                        RootToLeafPath[ctr].push_back(cost);
                        T++;
                }
        }

        void buildForCentroid(int u) {
                CentroidChildSubtreeSizes[u].push_back(0);
                int root_edges = 0, T = 0;
                for (auto v : E[u]) {
                        if (Level[v.x] > Level[u]) {
                                int begin = T;
                                dfs(v.x, u, u, ++root_edges, v.y, T);
                                int end = T;
                                EdgeToCtr[ {u, v.x}].push_back({{u, root_edges}, {begin, end - 1}});
                                EdgeToCtr[ {v.x, u}].push_back({{u, root_edges}, {begin, end - 1}});
                                CentroidChildSubtreeSizes[u].push_back(T);
                        }
                }

                if (root_edges > 0) {
                        LeafDepths[u].setup(RootToLeafPath[u], 0LL);
                        for (int i = 1; i <= root_edges; ++i) {
                                CtrMax[u].insert(maxForRootEdge(u, i));
                        }
                        AllMax.insert(maxForCentroid(u));
                }
        }

        ll maxForRootEdge(int u, int i) {
                return LeafDepths[u].get(CentroidChildSubtreeSizes[u][i - 1], CentroidChildSubtreeSizes[u][i] - 1);
        }

        ll maxForCentroid(int u) {
                if (CtrMax[u].empty()) {
                        return 0LL;
                } else if (CtrMax[u].size() == 1) {
                        return *CtrMax[u].rbegin();
                } else {
                        return *CtrMax[u].rbegin() + *next(CtrMax[u].rbegin());
                }
        }

        void remove(multiset<ll>&M, ll x) {
                M.erase(M.find(x));
        }

        void solve(istream& cin, ostream& cout) {
                int N, Q; ll W;
                cin >> N >> Q >> W;
                vector<pair<int, int> > _edges;
                vector<ll> _edge_w;

                E.resize(N);
                _edges.resize(N);
                _edge_w.resize(N);

                RootToLeafPath.resize(N);
                CentroidChildSubtreeSizes.resize(N);
                LeafDepths.resize(N);
                CtrMax.resize(N);
                for (int i = 0; i < N - 1; ++i) {
                        int a, b;
                        ll c;
                        
                        cin >> a >> b >> c;
                        --a;
                        --b;
                        _edges[i] = {a, b};
                        _edge_w[i] = c;
                        E[a].emplace_back(b, c);
                        E[b].emplace_back(a, c);
                }


                CentroidDecomposition<pair<int, ll>> C{E};
                Level = C.findCentroids();
                for (int i = 0; i < N; ++i) {
                        buildForCentroid(i);
                }

                ll last = 0; //*AllMax.rbegin();
                int cnt = 0;
                for (int q = 0; q < Q; ++q) {
                        int i;
                        ll c;
                        cin >> i >> c;
                        i = (i + last) % (N - 1);
                        c = (c + last) % W;
                        auto [a, b] = _edges[i];
                        ll rel_c = c - _edge_w[i];
                        _edge_w[i] = c;

                        // process (a,b) in all centroids in which this edge exists
                        for (auto e : EdgeToCtr[ {a, b}]) {
                                int ctr = e.x.x;
                                int i = e.x.y;
                                int l = e.y.x;
                                int r = e.y.y;

                                remove(AllMax, maxForCentroid(ctr));
                                remove(CtrMax[ctr], maxForRootEdge(ctr, i));

                                LeafDepths[ctr].put(l, r, rel_c);

                                CtrMax[ctr].insert(maxForRootEdge(ctr, i));
                                AllMax.insert(maxForCentroid(ctr));
                        }

                        ll cur = *AllMax.rbegin();
                        cout << cur << '\n';
                        //cnt += last != cur;
                        last = cur;
                }
                //cerr << cnt << '\n';
        }
};


int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        Diameter solver;
        std::istream& in(std::cin);
        std::ostream& out(std::cout);
        solver.solve(in, out);
        return 0;
}

Compilation message

diameter.cpp: In member function 'void Diameter::solve(std::istream&, std::ostream&)':
diameter.cpp:443:21: warning: unused variable 'cnt' [-Wunused-variable]
                 int cnt = 0;
                     ^~~
diameter.cpp: In instantiation of 'DFSOrder<EdgeType>::DFSOrder(const std::vector<std::vector<_Tp> >&) [with EdgeType = std::pair<int, long long int>]':
diameter.cpp:115:36:   required from 'const std::vector<int>& CentroidDecomposition<EdgeType>::findCentroids() [with EdgeType = std::pair<int, long long int>]'
diameter.cpp:437:41:   required from here
diameter.cpp:89:34: warning: 'DFSOrder<std::pair<int, long long int> >::RevEnter' will be initialized after [-Wreorder]
         vector<int> Enter, Exit, RevEnter;
                                  ^~~~~~~~
diameter.cpp:89:21: warning:   'std::vector<int> DFSOrder<std::pair<int, long long int> >::Enter' [-Wreorder]
         vector<int> Enter, Exit, RevEnter;
                     ^~~~~
diameter.cpp:42:9: warning:   when initialized here [-Wreorder]
         DFSOrder(const vector<vector<EdgeType>> &_E) : T(0), N(_E.size()), E(_E), RevEnter(N), Enter(N), Exit(N) {
         ^~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 3 ms 476 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 3 ms 476 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 26 ms 1272 KB Output is correct
20 Correct 29 ms 1400 KB Output is correct
21 Correct 33 ms 1372 KB Output is correct
22 Correct 28 ms 1400 KB Output is correct
23 Correct 60 ms 5340 KB Output is correct
24 Correct 76 ms 5908 KB Output is correct
25 Correct 81 ms 6492 KB Output is correct
26 Correct 73 ms 6312 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 312 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 18 ms 476 KB Output is correct
5 Correct 82 ms 828 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 5 ms 680 KB Output is correct
10 Correct 25 ms 764 KB Output is correct
11 Correct 113 ms 1116 KB Output is correct
12 Correct 14 ms 3384 KB Output is correct
13 Correct 12 ms 3368 KB Output is correct
14 Correct 15 ms 3340 KB Output is correct
15 Correct 38 ms 3512 KB Output is correct
16 Correct 168 ms 3944 KB Output is correct
17 Correct 290 ms 59852 KB Output is correct
18 Correct 308 ms 59872 KB Output is correct
19 Correct 281 ms 59796 KB Output is correct
20 Correct 342 ms 59876 KB Output is correct
21 Correct 711 ms 60580 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1400 KB Output is correct
2 Correct 39 ms 1528 KB Output is correct
3 Correct 162 ms 1724 KB Output is correct
4 Correct 333 ms 2004 KB Output is correct
5 Correct 81 ms 14956 KB Output is correct
6 Correct 131 ms 15128 KB Output is correct
7 Correct 349 ms 15332 KB Output is correct
8 Correct 627 ms 15592 KB Output is correct
9 Correct 600 ms 78884 KB Output is correct
10 Correct 660 ms 79128 KB Output is correct
11 Correct 1032 ms 79216 KB Output is correct
12 Correct 1448 ms 79688 KB Output is correct
13 Correct 1396 ms 161312 KB Output is correct
14 Correct 1471 ms 161500 KB Output is correct
15 Correct 1910 ms 161724 KB Output is correct
16 Correct 2389 ms 161944 KB Output is correct
17 Correct 4381 ms 162020 KB Output is correct

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3900 ms 130312 KB Output is correct
2 Correct 4184 ms 132016 KB Output is correct
3 Correct 4290 ms 131972 KB Output is correct
4 Correct 3924 ms 132548 KB Output is correct
5 Correct 3937 ms 127300 KB Output is correct
6 Correct 3135 ms 99016 KB Output is correct
7 Correct 4987 ms 144516 KB Output is correct
8 Correct 4884 ms 145560 KB Output is correct
9 Execution timed out 5028 ms 143672 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 3 ms 476 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 26 ms 1272 KB Output is correct
20 Correct 29 ms 1400 KB Output is correct
21 Correct 33 ms 1372 KB Output is correct
22 Correct 28 ms 1400 KB Output is correct
23 Correct 60 ms 5340 KB Output is correct
24 Correct 76 ms 5908 KB Output is correct
25 Correct 81 ms 6492 KB Output is correct
26 Correct 73 ms 6312 KB Output is correct
27 Correct 2 ms 312 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 4 ms 376 KB Output is correct
30 Correct 18 ms 476 KB Output is correct
31 Correct 82 ms 828 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 3 ms 632 KB Output is correct
34 Correct 3 ms 632 KB Output is correct
35 Correct 5 ms 680 KB Output is correct
36 Correct 25 ms 764 KB Output is correct
37 Correct 113 ms 1116 KB Output is correct
38 Correct 14 ms 3384 KB Output is correct
39 Correct 12 ms 3368 KB Output is correct
40 Correct 15 ms 3340 KB Output is correct
41 Correct 38 ms 3512 KB Output is correct
42 Correct 168 ms 3944 KB Output is correct
43 Correct 290 ms 59852 KB Output is correct
44 Correct 308 ms 59872 KB Output is correct
45 Correct 281 ms 59796 KB Output is correct
46 Correct 342 ms 59876 KB Output is correct
47 Correct 711 ms 60580 KB Output is correct
48 Correct 8 ms 1400 KB Output is correct
49 Correct 39 ms 1528 KB Output is correct
50 Correct 162 ms 1724 KB Output is correct
51 Correct 333 ms 2004 KB Output is correct
52 Correct 81 ms 14956 KB Output is correct
53 Correct 131 ms 15128 KB Output is correct
54 Correct 349 ms 15332 KB Output is correct
55 Correct 627 ms 15592 KB Output is correct
56 Correct 600 ms 78884 KB Output is correct
57 Correct 660 ms 79128 KB Output is correct
58 Correct 1032 ms 79216 KB Output is correct
59 Correct 1448 ms 79688 KB Output is correct
60 Correct 1396 ms 161312 KB Output is correct
61 Correct 1471 ms 161500 KB Output is correct
62 Correct 1910 ms 161724 KB Output is correct
63 Correct 2389 ms 161944 KB Output is correct
64 Correct 4381 ms 162020 KB Output is correct
65 Correct 3900 ms 130312 KB Output is correct
66 Correct 4184 ms 132016 KB Output is correct
67 Correct 4290 ms 131972 KB Output is correct
68 Correct 3924 ms 132548 KB Output is correct
69 Correct 3937 ms 127300 KB Output is correct
70 Correct 3135 ms 99016 KB Output is correct
71 Correct 4987 ms 144516 KB Output is correct
72 Correct 4884 ms 145560 KB Output is correct
73 Execution timed out 5028 ms 143672 KB Time limit exceeded
74 Halted 0 ms 0 KB -