Submission #770424

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
770424	2023-07-01T07:52:52 Z	JakobZorz	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	3903 ms	522552 KB

diameter

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>
#include <limits.h>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <map>
#include <cstring>
#include <sstream>
 
#pragma GCC target("popcnt")
 
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD = 1e9+7;
typedef pair<ld,ld> point;
#define x first
#define y second

//#define SEGTREE
//#define TREE
//#define DSU
//#define MATH
 
#ifdef SEGTREE
template<class Type>
class SegmentTree {
    Type (*func)(Type a, Type b);
    vector<Type> nodes;
    vector<int> l;
    vector<int> r;
    int size_log2;
    Type neutral;
    
    void init_node(int node) {
        if(node >= (1 << size_log2))
            return;
        
        l[2 * node] = l[node];
        r[2 * node] = (l[node] + r[node]) / 2;
        init_node(2 * node);
        
        l[2 * node + 1] = (l[node] + r[node]) / 2;
        r[2 * node + 1] = r[node];
        init_node(2 * node + 1);
        
        nodes[node] = func(nodes[2 * node], nodes[2 * node + 1]);
    }
    
    void update_node(int node) {
        if(node < (1 << size_log2))
            nodes[node] = func(nodes[2 * node], nodes[2 * node + 1]);
        
        if(node != 1)
            update_node(node / 2);
    }
    
    Type get(int node, int ll_, int rr) {
        if(rr <= l[node] || ll_ >= r[node])
            return neutral;
        
        if(ll_ <= l[node] && rr >= r[node])
            return nodes[node];
        
        Type left = get(2 * node, ll_, rr);
        Type right = get(2 * node + 1, ll_, rr);
        
        return func(left, right);
    }
    
public:
    SegmentTree(Type (*func)(Type a, Type b), vector<Type> vector, Type neutral) : func(func), neutral(neutral) {
        size_log2 = 0;
        while((1 << size_log2) < vector.size())
            size_log2++;
        
        nodes.resize((1 << size_log2) * 2);
        l.resize((1 << size_log2) * 2);
        r.resize((1 << size_log2) * 2);
        
        for(int i = 0; i < vector.size(); i++)
            nodes[(1 << size_log2) + i] = vector[i];
        
        l[1] = 0;
        r[1] = 1 << size_log2;
        init_node(1);
    }
    
    void set(int idx, Type el) {
        nodes[(1 << size_log2) + idx] = el;
        update_node((1 << size_log2) + idx);
    }
    
    Type get(int l, int r) {
        return get(1, l, r);
    }
    
    Type get(int idx) {
        return nodes[(1 << size_log2) + idx];
    }
    
    Type get() {
        return nodes[1];
    }
    
    int get_first_larger_or_eq_than(int bound) {
        return get_first_larger_or_eq_than(1, bound);
    }
    
    int get_first_larger_or_eq_than(int node, int bound) {
        if(node >= (1 << size_log2)) {
            return node - (1 << size_log2);
        }
        
        if(nodes[node * 2] > bound)
            return get_first_larger_or_eq_than(node * 2, bound);
        else
            return get_first_larger_or_eq_than(node * 2 + 1, bound - nodes[node * 2]);
    }
};
 
#endif
 
#ifdef TREE
#define POW 18
 
struct Node {
    int parents[POW];
    vector<int> conns;
    int depth;
    int value;
    int subtree_depth;
    int subtree_size;
    int euler;
    int val;
    int res;
};
 
ll add(ll a, ll b) {
    return a + b;
}
 
Node nodes[200000];
int n;
 
int setup(int node, int depth, int euler, ll dist) {
    dist += nodes[node].value;
    nodes[node].depth = depth;
    nodes[node].euler = euler++;
    
    
    for(int i = 1; i < POW; i++) {
        nodes[node].parents[i] = nodes[nodes[node].parents[i - 1]].parents[i - 1];
    }
    
    int size = 1;
    
    for(int i = 0; i < nodes[node].conns.size(); i++) {
        int child = nodes[node].conns[i];
        if(child != nodes[node].parents[0]) {
            nodes[child].parents[0] = node;
            euler = setup(child, depth + 1, euler, dist);
            size += nodes[child].subtree_size;
        }
    }
    nodes[node].subtree_size = size;
    return euler;
}
 
void setup_tree(int root) {
    nodes[root].parents[0] = root;
    setup(root, 0, 0, 0);
}
 
int get_subtree_depth(int node) {
    if(nodes[node].subtree_depth)
        return nodes[node].subtree_depth;
    
    int max_depth = 1;
    for(int child : nodes[node].conns) {
        if(child == nodes[node].parents[0])
            continue;
        max_depth = max(max_depth, get_subtree_depth(child) + 1);
    }
    nodes[node].subtree_depth = max_depth;
    return max_depth;
}
 
int get_parent(int node, int depth) {
    if(depth > nodes[node].depth)
        return -1;
    
    int climber = node;
    for(int i = 0; i < POW; i++) {
        if(depth & (1 << i) && climber != -1)
            climber = nodes[climber].parents[i];
    }
    
    return climber;
}

bool is_sub(int a,int b){
    return get_parent(a,nodes[a].depth-nodes[b].depth)==b;
}
 
int lca(int a, int b) {
    if(nodes[a].depth < nodes[b].depth)
        swap(a, b);
    
    a = get_parent(a, nodes[a].depth - nodes[b].depth);
    
    if(a == b)
        return a;
    
    for(int i = POW - 1; i >= 0; i--) {
        if(nodes[a].parents[i] != nodes[b].parents[i]) {
            a = nodes[a].parents[i];
            b = nodes[b].parents[i];
        }
    }
    
    return nodes[a].parents[0];
}
 
#endif
 
#ifdef DSU
 
class Dsu {
    vector<int> arr;
    int num_sets;
    
public:
    Dsu(int size) {
        arr = vector<int>(size, -1);
        num_sets = size;
    }
    
    int merge(int a, int b) {
        a = get(a);
        b = get(b);
        
        if(a == b)
            return a;
        
        if(arr[a] > arr[b])
            swap(a, b);
        
        arr[a] += arr[b];
        arr[b] = a;
        num_sets--;
        return a;
    }
    
    int get(int a) {
        if(arr[a] < 0)
            return a;
        arr[a] = get(arr[a]);
        return get(arr[a]);
    }
    
    int get_size(int a) {
        return -arr[get(a)];
    }
    
    int get_num_sets() {
        return num_sets;
    }
};
 
#endif
 
#ifdef MATH
 
ll dpf[2000001];
ll factorial(ll n) {
    if(n == 0)
        return 1;
    
    if(dpf[n])
        return dpf[n];
    
    ll result = factorial(n - 1) * n;
    result %= MOD;
    dpf[n] = result;
    return result;
}
 
ll powm(ll base, ll exp) {
    ll result = 1;
    
    for(int i = 0; i < 64; i++) {
        if((exp >> i) % 2 == 1) {
            result *= base;
            result %= MOD;
        }
        base *= base;
        base %= MOD;
    }
    
    return result;
}
 
ll inverse(ll n) {
    return powm(n, MOD - 2);
}
 
ll dpif[2000001];
ll inverse_factorial(ll n) {
    if(dpif[n])
        return dpif[n];
    
    ll result = inverse(factorial(n));
    dpif[n] = result;
    return result;
}
 
ll choose(ll n, ll k) {
    return (((factorial(n)*inverse_factorial(n-k))%MOD)*inverse_factorial(k))%MOD;
}
 
ll gcd(ll a, ll b){
    if(a==b)
        return a;
    if(a<b)
        swap(a,b);
    if(b==0)
        return a;
    return gcd(b, a%b);
}
 
#endif

class Arr{
    vector<ll>tree;
    vector<int>l,r;
    vector<ll>lazy;
    int tree_size;
    void init_node(int node,int left,int right){
        int mid=(left+right)/2;
        l[node]=left;
        r[node]=right;
        if(node<tree_size){
            init_node(2*node,left,mid);
            init_node(2*node+1,mid,right);
            tree[node]=max(tree[2*node],tree[2*node+1]);
        }
    }
    
    void push_node(int node){
        tree[node]+=lazy[node];
        if(node<tree_size){
            lazy[2*node]+=lazy[node];
            lazy[2*node+1]+=lazy[node];
        }
        lazy[node]=0;
    }
    
    ll get_max_node(int node,int left,int right){
        push_node(node);
        if(left<=l[node]&&r[node]<=right)
            return tree[node];
        
        if(r[node]<=left||right<=l[node])
            return 0;
        
        return max(get_max_node(2*node,left,right),get_max_node(2*node+1,left,right));
    }
    
    void inc_node(int node,int left,int right,ll s){
        push_node(node);
        if(left<=l[node]&&r[node]<=right){
            lazy[node]+=s;
            push_node(node);
            return;
        }
        
        if(r[node]<=left||right<=l[node])
            return;
        
        inc_node(2*node,left,right,s);
        inc_node(2*node+1,left,right,s);
        tree[node]=max(tree[2*node],tree[2*node+1]);
    }
    
public:
    Arr(vector<ll>v){
        tree_size=1;
        while(tree_size<(int)v.size())
            tree_size*=2;
        tree.resize(2*tree_size);
        for(int i=0;i<(int)v.size();i++)
            tree[tree_size+i]=v[i];
        l.resize(2*tree_size);
        r.resize(2*tree_size);
        lazy.resize(2*tree_size);
        init_node(1,0,tree_size);
    }
    
    Arr()=default;
    
    ll get_max(int l,int r){
        return get_max_node(1,l,r);
    }
    
    void inc(int l,int r,ll c){
        inc_node(1,l,r,c);
    }
};

class Context{
    int curr=1;
    unordered_map<int,int>m;
public:
    void add(int a){
        if(m[a]==0)
            m[a]=curr++;
    }
    
    int get(int a){
        return m[a]-1;
    }
    
    bool has(int a){
        return m[a]!=0;
    }
};

class Tree{
    Context context;
    vector<ll>leaves_vec;
    Arr leaves;
    vector<int>leaves_l;
    vector<int>leaves_r;
    vector<vector<pair<int,ll>>>nodes;
    vector<int>parents;
    vector<int>parent_root;
    vector<int>parent_root_idx;
    vector<ll>parentsw;
    vector<vector<int>>children;
    multiset<ll>root_children,subtree_res;
    vector<Tree*>subtrees;
    int n,root;
    vector<int>conns1;
    vector<int>conns2;
    vector<ll>conns3;
    ll prev_res=0;
    
    void init_node(int node,int par,ll d){
        parents[node]=par;
        leaves_l[node]=10000000;
        leaves_r[node]=0;
        for(pair<int,ll> ch:nodes[node]){
            if(ch.first==par){
                parentsw[node]=ch.second;
                continue;
            }
            
            init_node(ch.first,node,d+ch.second);
            children[node].push_back(ch.first);
            leaves_l[node]=min(leaves_l[node],leaves_l[ch.first]);
            leaves_r[node]=max(leaves_r[node],leaves_r[ch.first]);
        }
        if(children[node].empty()){
            leaves_l[node]=(int)leaves_vec.size();
            leaves_r[node]=(int)leaves_vec.size()+1;
            leaves_vec.push_back(d);
        }
    }
    
    void init_node_2(int node,int par_root,int par_root_idx){
        parent_root[node]=par_root;
        parent_root_idx[node]=par_root_idx;
        for(int ch:children[node])
            init_node_2(ch,par_root,par_root_idx);
    }
    
    void get_conns(int node){
        for(int ch:children[node]){
            conns1.push_back(node);
            conns2.push_back(ch);
            conns3.push_back(parentsw[ch]);
            get_conns(ch);
        }
    }
    
    vector<vector<int>>children2;
    vector<int>subtree_size;
    void init_node_3(int node,int par){
        subtree_size[node]=1;
        for(pair<int,ll>ne:nodes[node]){
            if(ne.first==par)
                continue;
            init_node_3(ne.first,node);
            children2[node].push_back(ne.first);
            subtree_size[node]+=subtree_size[ne.first];
        }
    }
    
    int get_centroid(){
        init_node_3(0,-1);
        int curr=0;
        while(true){
            int prev=curr;
            for(int ch:children2[curr])
                if(subtree_size[ch]>=n/2){
                    curr=ch;
                    break;
                }
            if(prev==curr)
                break;
        }
        return curr;
    }
    
public:
    Tree(int n):n(n){
        if(n<=1)
            return;
        nodes.resize(n);
        parents.resize(n);
        parentsw.resize(n);
        children.resize(n);
        leaves_l.resize(n);
        leaves_r.resize(n);
        parent_root.resize(n);
        children2.resize(n);
        subtree_size.resize(n);
        parent_root_idx.resize(n);
    }
    
    void add_edge(int a,int b,ll c){
        context.add(a);
        context.add(b);
        a=context.get(a);
        b=context.get(b);
        nodes[a].emplace_back(b,c);
        nodes[b].emplace_back(a,c);
    }
    
    void init_tree(){
        if(n<=1)
            return;
        root=get_centroid();
        init_node(root,-1,0);
        leaves=Arr(leaves_vec);
        int i=0;
        for(int ch:children[root]){
            init_node_2(ch,ch,i);
            root_children.insert(leaves.get_max(leaves_l[ch],leaves_r[ch]));
            conns1.clear();
            conns2.clear();
            conns3.clear();
            get_conns(ch);
            subtrees.push_back(new Tree((int)conns1.size()+1));
            for(int i=0;i<(int)conns1.size();i++)
                subtrees.back()->add_edge(conns1[i],conns2[i],conns3[i]);
            subtrees.back()->init_tree();
            i++;
        }
        ll res=0;
        if(root_children.size()==1)
            res=*--root_children.end();
        else
            res=*--root_children.end()+*--(--root_children.end());
        
        for(Tree*tree:subtrees){
            ll res2=tree->prev_res;
            res=max(res,res2);
            subtree_res.insert(res2);
        }
        prev_res=res;
    }
    
    ll set_edge(int a,int b,ll c){
        //cout<<"set: "<<a<<" "<<b<<"\n";
        if(!context.has(a)||!context.has(b)||n<=1)
            return prev_res;
        
        a=context.get(a);
        b=context.get(b);
        
        // b is parent of a
        if(parents[a]!=b)
            swap(a,b);
        
        int root_ch=parent_root[a];
        root_children.erase(root_children.find(leaves.get_max(leaves_l[root_ch],leaves_r[root_ch])));
        
        ll diff=c-parentsw[a];
        parentsw[a]=c;
        leaves.inc(leaves_l[a],leaves_r[a],diff);
        
        root_children.insert(leaves.get_max(leaves_l[root_ch],leaves_r[root_ch]));
        
        ll res=0;
        if(root_children.size()==1)
            res=*--root_children.end();
        else
            res=*--root_children.end()+*--(--root_children.end());
        
        int subtree=parent_root_idx[a];
        
        subtree_res.erase(subtree_res.find(subtrees[subtree]->prev_res));
        subtree_res.insert(subtrees[subtree]->set_edge(a,b,c));
        res=max(res,*--subtree_res.end());
        /*for(Tree*tree:subtrees){
            ll res2=tree->set_edge(a,b,c);
            res=max(res,res2);
        }*/
        prev_res=res;
        //cout<<"res: "<<res<<"\n";
        return res;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    //freopen("speeding.in","r",stdin);
    //freopen("speeding.out","w",stdout);
    
    ll n,q,w;
    vector<pair<int,int>> edges;
    cin>>n>>q>>w;
    edges.resize(n-1);
    Tree tree((int)n);
    
    for(int i=0;i<n-1;i++){
        int a,b;
        ll c;
        cin>>a>>b>>c;
        a--;b--;
        edges[i]={a,b};
        tree.add_edge(a,b,c);
    }
    
    tree.init_tree();
    
    ll last=0;
    while(q--){
        ll d,e;
        cin>>d>>e;
        d=(d+last)%(n-1);
        e=(e+last)%w;
        last=tree.set_edge(edges[d].first,edges[d].second,e);
        cout<<last<<"\n";
    }
    
    return 0;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	324 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	1 ms	452 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	1 ms	468 KB	Output is correct
17	Correct	1 ms	468 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct

Subtask #2

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	324 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	1 ms	452 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	1 ms	468 KB	Output is correct
17	Correct	1 ms	468 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	16 ms	2832 KB	Output is correct
20	Correct	17 ms	3072 KB	Output is correct
21	Correct	19 ms	3284 KB	Output is correct
22	Correct	13 ms	3796 KB	Output is correct
23	Correct	41 ms	13936 KB	Output is correct
24	Correct	48 ms	16668 KB	Output is correct
25	Correct	57 ms	18328 KB	Output is correct
26	Correct	42 ms	20764 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	12 ms	456 KB	Output is correct
5	Correct	57 ms	1360 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	832 KB	Output is correct
8	Correct	1 ms	852 KB	Output is correct
9	Correct	3 ms	852 KB	Output is correct
10	Correct	18 ms	1108 KB	Output is correct
11	Correct	88 ms	2120 KB	Output is correct
12	Correct	6 ms	5476 KB	Output is correct
13	Correct	6 ms	5588 KB	Output is correct
14	Correct	11 ms	5692 KB	Output is correct
15	Correct	31 ms	6520 KB	Output is correct
16	Correct	128 ms	7688 KB	Output is correct
17	Correct	170 ms	103860 KB	Output is correct
18	Correct	183 ms	103836 KB	Output is correct
19	Correct	172 ms	104064 KB	Output is correct
20	Correct	225 ms	105520 KB	Output is correct
21	Correct	583 ms	114380 KB	Output is correct

Subtask #4

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	3028 KB	Output is correct
2	Correct	23 ms	3288 KB	Output is correct
3	Correct	94 ms	3804 KB	Output is correct
4	Correct	182 ms	4564 KB	Output is correct
5	Correct	43 ms	34092 KB	Output is correct
6	Correct	78 ms	34524 KB	Output is correct
7	Correct	231 ms	35432 KB	Output is correct
8	Correct	420 ms	36468 KB	Output is correct
9	Correct	282 ms	202064 KB	Output is correct
10	Correct	331 ms	202396 KB	Output is correct
11	Correct	584 ms	203652 KB	Output is correct
12	Correct	958 ms	204840 KB	Output is correct
13	Correct	435 ms	397064 KB	Output is correct
14	Correct	550 ms	397880 KB	Output is correct
15	Correct	905 ms	399592 KB	Output is correct
16	Correct	1323 ms	401292 KB	Output is correct
17	Correct	2492 ms	404336 KB	Output is correct

Subtask #5

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2679 ms	389756 KB	Output is correct
2	Correct	2810 ms	399876 KB	Output is correct
3	Correct	2705 ms	397380 KB	Output is correct
4	Correct	2841 ms	402948 KB	Output is correct
5	Correct	2640 ms	375772 KB	Output is correct
6	Correct	2362 ms	263248 KB	Output is correct
7	Correct	3646 ms	497408 KB	Output is correct
8	Correct	3903 ms	497480 KB	Output is correct
9	Correct	3417 ms	497556 KB	Output is correct
10	Correct	3457 ms	494764 KB	Output is correct
11	Correct	3373 ms	468076 KB	Output is correct
12	Correct	2808 ms	324184 KB	Output is correct
13	Correct	2330 ms	522548 KB	Output is correct
14	Correct	2406 ms	522524 KB	Output is correct
15	Correct	2438 ms	522552 KB	Output is correct
16	Correct	2490 ms	520048 KB	Output is correct
17	Correct	2313 ms	490412 KB	Output is correct
18	Correct	2120 ms	320228 KB	Output is correct
19	Correct	2314 ms	522480 KB	Output is correct
20	Correct	2507 ms	522456 KB	Output is correct
21	Correct	2315 ms	522524 KB	Output is correct
22	Correct	2377 ms	520076 KB	Output is correct
23	Correct	2301 ms	490364 KB	Output is correct
24	Correct	2017 ms	333824 KB	Output is correct

Subtask #6

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	324 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	1 ms	452 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	1 ms	468 KB	Output is correct
17	Correct	1 ms	468 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	16 ms	2832 KB	Output is correct
20	Correct	17 ms	3072 KB	Output is correct
21	Correct	19 ms	3284 KB	Output is correct
22	Correct	13 ms	3796 KB	Output is correct
23	Correct	41 ms	13936 KB	Output is correct
24	Correct	48 ms	16668 KB	Output is correct
25	Correct	57 ms	18328 KB	Output is correct
26	Correct	42 ms	20764 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	2 ms	332 KB	Output is correct
30	Correct	12 ms	456 KB	Output is correct
31	Correct	57 ms	1360 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Correct	1 ms	832 KB	Output is correct
34	Correct	1 ms	852 KB	Output is correct
35	Correct	3 ms	852 KB	Output is correct
36	Correct	18 ms	1108 KB	Output is correct
37	Correct	88 ms	2120 KB	Output is correct
38	Correct	6 ms	5476 KB	Output is correct
39	Correct	6 ms	5588 KB	Output is correct
40	Correct	11 ms	5692 KB	Output is correct
41	Correct	31 ms	6520 KB	Output is correct
42	Correct	128 ms	7688 KB	Output is correct
43	Correct	170 ms	103860 KB	Output is correct
44	Correct	183 ms	103836 KB	Output is correct
45	Correct	172 ms	104064 KB	Output is correct
46	Correct	225 ms	105520 KB	Output is correct
47	Correct	583 ms	114380 KB	Output is correct
48	Correct	6 ms	3028 KB	Output is correct
49	Correct	23 ms	3288 KB	Output is correct
50	Correct	94 ms	3804 KB	Output is correct
51	Correct	182 ms	4564 KB	Output is correct
52	Correct	43 ms	34092 KB	Output is correct
53	Correct	78 ms	34524 KB	Output is correct
54	Correct	231 ms	35432 KB	Output is correct
55	Correct	420 ms	36468 KB	Output is correct
56	Correct	282 ms	202064 KB	Output is correct
57	Correct	331 ms	202396 KB	Output is correct
58	Correct	584 ms	203652 KB	Output is correct
59	Correct	958 ms	204840 KB	Output is correct
60	Correct	435 ms	397064 KB	Output is correct
61	Correct	550 ms	397880 KB	Output is correct
62	Correct	905 ms	399592 KB	Output is correct
63	Correct	1323 ms	401292 KB	Output is correct
64	Correct	2492 ms	404336 KB	Output is correct
65	Correct	2679 ms	389756 KB	Output is correct
66	Correct	2810 ms	399876 KB	Output is correct
67	Correct	2705 ms	397380 KB	Output is correct
68	Correct	2841 ms	402948 KB	Output is correct
69	Correct	2640 ms	375772 KB	Output is correct
70	Correct	2362 ms	263248 KB	Output is correct
71	Correct	3646 ms	497408 KB	Output is correct
72	Correct	3903 ms	497480 KB	Output is correct
73	Correct	3417 ms	497556 KB	Output is correct
74	Correct	3457 ms	494764 KB	Output is correct
75	Correct	3373 ms	468076 KB	Output is correct
76	Correct	2808 ms	324184 KB	Output is correct
77	Correct	2330 ms	522548 KB	Output is correct
78	Correct	2406 ms	522524 KB	Output is correct
79	Correct	2438 ms	522552 KB	Output is correct
80	Correct	2490 ms	520048 KB	Output is correct
81	Correct	2313 ms	490412 KB	Output is correct
82	Correct	2120 ms	320228 KB	Output is correct
83	Correct	2314 ms	522480 KB	Output is correct
84	Correct	2507 ms	522456 KB	Output is correct
85	Correct	2315 ms	522524 KB	Output is correct
86	Correct	2377 ms	520076 KB	Output is correct
87	Correct	2301 ms	490364 KB	Output is correct
88	Correct	2017 ms	333824 KB	Output is correct
89	Correct	2648 ms	394760 KB	Output is correct
90	Correct	2978 ms	436208 KB	Output is correct
91	Correct	3444 ms	484740 KB	Output is correct
92	Correct	3403 ms	496756 KB	Output is correct
93	Correct	3282 ms	509728 KB	Output is correct
94	Correct	2962 ms	515572 KB	Output is correct
95	Correct	2384 ms	521852 KB	Output is correct
96	Correct	2329 ms	521788 KB	Output is correct
97	Correct	2359 ms	521832 KB	Output is correct
98	Correct	2318 ms	521884 KB	Output is correct
99	Correct	2288 ms	521788 KB	Output is correct
100	Correct	2293 ms	521800 KB	Output is correct