oj.uz

Submission #877789

# Submission time Handle Problem Language Result Execution time Memory
877789 2023-11-23T14:34:20 Z simona1230 Jail (JOI22_jail) C++17
100 / 100
 1384 ms 220876 KB 
#include <bits/stdc++.h>
#define endl "\n"

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target(avx2)

using namespace std;
const int maxver=1e6;
const int maxn=9*120000;
int q,n,m;
vector<int> f[maxn];
void read()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        f[i].clear();
    for(int i=1; i<n; i++)
    {
        int x,y;
        cin>>x>>y;
        f[x].push_back(y);
        f[y].push_back(x);
    }
    cin>>m;
}

int num;
int ts[maxn];
int te[maxn];
int dw[maxn];
int up[maxn];

vector<int> v[maxver],o[maxver];

void add_edge(int x,int y)
{
    v[x].push_back(y);
    o[y].push_back(x);
}

void make_tree(int i,int l,int r)
{
    if(l==r)
    {
        ts[i]=num++;
        te[i]=num++;
        //cout<<ts[i]<<" "<<te[i]<<" "<<l<<" "<<r<<endl;
        dw[l]=ts[i];
        up[l]=te[i];
        return;
    }

    ts[i]=num++;
    te[i]=num++;
    //cout<<ts[i]<<" "<<te[i]<<" "<<l<<" "<<r<<endl;
    int mid=(l+r)/2;

    make_tree(i*2,l,mid);
    make_tree(i*2+1,mid+1,r);

    add_edge(ts[i],ts[i*2]);
    add_edge(ts[i],ts[i*2+1]);
    add_edge(te[i*2],te[i]);
    add_edge(te[i*2+1],te[i]);
}

int used[maxn];
int sz[maxn];

void size_(int i)
{
    used[i]=1;
    sz[i]=1;
    for(int j=0; j<f[i].size(); j++)
    {
        int nb=f[i][j];
        if(!used[nb])
        {
            size_(nb);
            sz[i]+=sz[nb];
        }
    }
}

int jump[maxn][21];

int pos[maxn];
int chain[maxn];
int lvl[maxn];
int cnt=1;

void hld(int i,int lead,int level,int par)
{
    pos[i]=cnt++;
    chain[i]=lead;
    lvl[i]=level;

    int maxx=0,big=0;
    for(int j=0; j<f[i].size(); j++)
    {
        int nb=f[i][j];
        if(sz[nb]>maxx&&nb!=par)
        {
            maxx=sz[nb];
            big=nb;
        }
    }

    if(big)
    {
        //cout<<"here "<<i<<" "<<lead<<" "<<ver<<endl;
        hld(big,lead,level+1,i);
        jump[big][0]=i;
    }

    for(int j=0; j<f[i].size(); j++)
    {
        int nb=f[i][j];
        if(nb!=big&&nb!=par)
        {
            hld(nb,nb,level+1,i);
            jump[nb][0]=i;
        }
    }
}

void prec()
{
    for(int j=1; j<=20; j++)
        for(int i=1; i<=n; i++)
            jump[i][j]=jump[jump[i][j-1]][j-1];
}

int make_jump(int x,int k)
{
    for(int i=20; i>=0; i--)
        if(k&(1<<i))x=jump[x][i];
    return x;
}

int lca(int x,int y)
{
    if(lvl[x]<lvl[y])swap(x,y);
    x=make_jump(x,abs(lvl[x]-lvl[y]));
    if(x==y)return x;

    for(int i=20; i>=0; i--)
    {
        if(jump[x][i]!=jump[y][i])
        {
            x=jump[x][i];
            y=jump[y][i];
        }
    }

    return jump[x][0];
}

void update(int i,int l,int r,int ql,int qr,int pr)
{
    if(ql>qr||r<ql||l>qr)return;

    if(ql<=l&&r<=qr)
    {
        add_edge(pr,ts[i]);
        add_edge(te[i],pr);
        return;
    }

    int mid=(l+r)/2;
    update(i*2,l,mid,ql,qr,pr);
    update(i*2+1,mid+1,r,ql,qr,pr);
}
void make_graph()
{
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin>>x>>y;
        add_edge(dw[pos[x]],i);
        add_edge(i,up[pos[y]]);

        int st,lca_=lca(x,y);
        //cout<<lca_<<endl;

        st=x;
        while(true)
        {
            int ed=chain[st];
            if(lvl[ed]<lvl[lca_])ed=lca_;
            update(1,1,n,pos[ed],pos[st],i);
            //cout<<pos[ed]<<" "<<pos[st]<<endl;
            if(ed==lca_)break;
            st=jump[ed][0];
        }

        st=y;
        while(true)
        {
            int ed=chain[st];
            if(lvl[ed]<lvl[lca_])ed=lca_;
            update(1,1,n,pos[ed],pos[st],i);
            //cout<<pos[ed]<<" "<<pos[st]<<endl;
            if(ed==lca_)break;
            st=jump[ed][0];
        }
    }
}

int comp;
stack<int> topo;
int used1[maxn];
int used2[maxn];

void dfs1(int i)
{
    used1[i]=1;
    for(int j=0; j<v[i].size(); j++)
    {
        int nb=v[i][j];
        if(!used1[nb])
            dfs1(nb);
    }
    topo.push(i);
}

void dfs2(int i)
{
    used2[i]=comp;
    for(int j=0; j<o[i].size(); j++)
    {
        int nb=o[i][j];
        if(!used2[nb])
            dfs2(nb);
    }
}

bool usedf[maxn];

void check()
{
    ///mp.clear();
    for(int i=1; i<=m; i++)
        if(!used1[i])dfs1(i);

    comp=0;
    while(topo.size())
    {
        int ver=topo.top();
        topo.pop();
        if(!used2[ver])
        {
            comp++;
            dfs2(ver);
        }
    }
    //cout<<comp<<" "<<num<<endl;
    bool ans=1;
    for(int i=1;i<=m;i++)
    {
        if(usedf[used2[i]] == true) ans = false;
        usedf[used2[i]] = true;

    }
    if(ans)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>q;
    while(q--)
    {
        read();

        for(int i=1; i<= num; i++)
        {
            v[i].clear();
            o[i].clear();
        }
        for(int i=1;i<maxn;i++)
        {
            /**used[i]=pos[i]=used1[i]=0;
            used2[i]=chain[i]=ts[i]=0;
            te[i]=sz[i]=dw[i]=up[i]=lvl[i]=0;*/

            used[i] = 0;
            used1[i] = 0;
            used2[i] = 0;
            usedf[i] = 0;


        }
        /*memset(used,0,sizeof(used));
        memset(pos,0,sizeof(pos));
        memset(used1,0,sizeof(used1));
        memset(used2,0,sizeof(used2));
        memset(chain,0,sizeof(chain));
        memset(ts,0,sizeof(ts));
        memset(te,0,sizeof(te));
        memset(sz,0,sizeof(sz));
        memset(dw,0,sizeof(dw));
        memset(up,0,sizeof(up));
        memset(lvl,0,sizeof(lvl));*/
        /**for(int i=1; i<=n; i++)
            for(int j=0; j<=20; j++)
                jump[i][j]=0;*/

        size_(1);
        cnt=1;
        hld(1,1,1,-1);
        prec();
        num=m+1;
        make_tree(1,1,n);
        make_graph();
        /*for(int i=1;i<num;i++)
        {
            cout<<i<<": ";
            for(int j=0;j<v[i].size();j++)
            {
                cout<<v[i][j]<<" ";
            }
            cout<<endl;
        }*/
        check();
    }
    return 0;
}
/*
1
6
2 4
4 1
1 5
5 3
3 6
2
2 3
6 1
*/

Compilation message

jail.cpp:5:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
    5 | #pragma GCC target(avx2)
      |                    ^~~~
jail.cpp: In function 'void size_(int)':
jail.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int j=0; j<f[i].size(); j++)
      |                  ~^~~~~~~~~~~~
jail.cpp: In function 'void hld(int, int, int, int)':
jail.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int j=0; j<f[i].size(); j++)
      |                  ~^~~~~~~~~~~~
jail.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for(int j=0; j<f[i].size(); j++)
      |                  ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs1(int)':
jail.cpp:218:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |     for(int j=0; j<v[i].size(); j++)
      |                  ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs2(int)':
jail.cpp:230:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |     for(int j=0; j<o[i].size(); j++)
      |                  ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 104284 KB Output is correct
2 Correct 22 ms 104376 KB Output is correct
3 Correct 20 ms 104284 KB Output is correct
4 Correct 222 ms 104468 KB Output is correct
5 Correct 446 ms 104480 KB Output is correct
6 Correct 30 ms 104280 KB Output is correct
7 Correct 32 ms 104284 KB Output is correct
8 Correct 31 ms 104536 KB Output is correct
9 Correct 84 ms 108680 KB Output is correct
10 Correct 127 ms 153940 KB Output is correct
11 Correct 464 ms 104448 KB Output is correct
12 Correct 495 ms 104844 KB Output is correct
13 Correct 251 ms 164692 KB Output is correct
14 Correct 248 ms 167096 KB Output is correct
15 Correct 557 ms 176720 KB Output is correct
16 Correct 1116 ms 214960 KB Output is correct
17 Correct 301 ms 182384 KB Output is correct
18 Correct 253 ms 176952 KB Output is correct
19 Correct 304 ms 178636 KB Output is correct
20 Correct 295 ms 178856 KB Output is correct
21 Correct 357 ms 181136 KB Output is correct
22 Correct 202 ms 163888 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 104284 KB Output is correct
2 Correct 20 ms 104448 KB Output is correct
3 Correct 32 ms 104284 KB Output is correct
4 Correct 31 ms 104284 KB Output is correct
5 Correct 32 ms 104508 KB Output is correct
6 Correct 31 ms 104284 KB Output is correct
7 Correct 30 ms 104284 KB Output is correct
8 Correct 30 ms 104280 KB Output is correct
9 Correct 29 ms 104280 KB Output is correct
10 Correct 31 ms 104284 KB Output is correct
11 Correct 30 ms 104280 KB Output is correct
12 Correct 31 ms 104284 KB Output is correct
13 Correct 30 ms 104388 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 104284 KB Output is correct
2 Correct 20 ms 104448 KB Output is correct
3 Correct 32 ms 104284 KB Output is correct
4 Correct 31 ms 104284 KB Output is correct
5 Correct 32 ms 104508 KB Output is correct
6 Correct 31 ms 104284 KB Output is correct
7 Correct 30 ms 104284 KB Output is correct
8 Correct 30 ms 104280 KB Output is correct
9 Correct 29 ms 104280 KB Output is correct
10 Correct 31 ms 104284 KB Output is correct
11 Correct 30 ms 104280 KB Output is correct
12 Correct 31 ms 104284 KB Output is correct
13 Correct 30 ms 104388 KB Output is correct
14 Correct 22 ms 104388 KB Output is correct
15 Correct 23 ms 104284 KB Output is correct
16 Correct 30 ms 104280 KB Output is correct
17 Correct 32 ms 104284 KB Output is correct
18 Correct 30 ms 104280 KB Output is correct
19 Correct 31 ms 104284 KB Output is correct
20 Correct 32 ms 104284 KB Output is correct
21 Correct 31 ms 104284 KB Output is correct
22 Correct 30 ms 104284 KB Output is correct
23 Correct 35 ms 104456 KB Output is correct
24 Correct 32 ms 104284 KB Output is correct
25 Correct 39 ms 104284 KB Output is correct
26 Correct 33 ms 104284 KB Output is correct
27 Correct 31 ms 104284 KB Output is correct
28 Correct 29 ms 104536 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 104284 KB Output is correct
2 Correct 20 ms 104448 KB Output is correct
3 Correct 32 ms 104284 KB Output is correct
4 Correct 31 ms 104284 KB Output is correct
5 Correct 32 ms 104508 KB Output is correct
6 Correct 31 ms 104284 KB Output is correct
7 Correct 30 ms 104284 KB Output is correct
8 Correct 30 ms 104280 KB Output is correct
9 Correct 29 ms 104280 KB Output is correct
10 Correct 31 ms 104284 KB Output is correct
11 Correct 30 ms 104280 KB Output is correct
12 Correct 31 ms 104284 KB Output is correct
13 Correct 30 ms 104388 KB Output is correct
14 Correct 22 ms 104388 KB Output is correct
15 Correct 23 ms 104284 KB Output is correct
16 Correct 30 ms 104280 KB Output is correct
17 Correct 32 ms 104284 KB Output is correct
18 Correct 30 ms 104280 KB Output is correct
19 Correct 31 ms 104284 KB Output is correct
20 Correct 32 ms 104284 KB Output is correct
21 Correct 31 ms 104284 KB Output is correct
22 Correct 30 ms 104284 KB Output is correct
23 Correct 35 ms 104456 KB Output is correct
24 Correct 32 ms 104284 KB Output is correct
25 Correct 39 ms 104284 KB Output is correct
26 Correct 33 ms 104284 KB Output is correct
27 Correct 31 ms 104284 KB Output is correct
28 Correct 29 ms 104536 KB Output is correct
29 Correct 33 ms 104540 KB Output is correct
30 Correct 34 ms 104524 KB Output is correct
31 Correct 34 ms 104536 KB Output is correct
32 Correct 35 ms 104544 KB Output is correct
33 Correct 32 ms 104280 KB Output is correct
34 Correct 33 ms 104540 KB Output is correct
35 Correct 33 ms 104540 KB Output is correct
36 Correct 32 ms 104508 KB Output is correct
37 Correct 31 ms 104540 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 104284 KB Output is correct
2 Correct 20 ms 104448 KB Output is correct
3 Correct 32 ms 104284 KB Output is correct
4 Correct 31 ms 104284 KB Output is correct
5 Correct 32 ms 104508 KB Output is correct
6 Correct 31 ms 104284 KB Output is correct
7 Correct 30 ms 104284 KB Output is correct
8 Correct 30 ms 104280 KB Output is correct
9 Correct 29 ms 104280 KB Output is correct
10 Correct 31 ms 104284 KB Output is correct
11 Correct 30 ms 104280 KB Output is correct
12 Correct 31 ms 104284 KB Output is correct
13 Correct 30 ms 104388 KB Output is correct
14 Correct 22 ms 104388 KB Output is correct
15 Correct 23 ms 104284 KB Output is correct
16 Correct 30 ms 104280 KB Output is correct
17 Correct 32 ms 104284 KB Output is correct
18 Correct 30 ms 104280 KB Output is correct
19 Correct 31 ms 104284 KB Output is correct
20 Correct 32 ms 104284 KB Output is correct
21 Correct 31 ms 104284 KB Output is correct
22 Correct 30 ms 104284 KB Output is correct
23 Correct 35 ms 104456 KB Output is correct
24 Correct 32 ms 104284 KB Output is correct
25 Correct 39 ms 104284 KB Output is correct
26 Correct 33 ms 104284 KB Output is correct
27 Correct 31 ms 104284 KB Output is correct
28 Correct 29 ms 104536 KB Output is correct
29 Correct 33 ms 104540 KB Output is correct
30 Correct 34 ms 104524 KB Output is correct
31 Correct 34 ms 104536 KB Output is correct
32 Correct 35 ms 104544 KB Output is correct
33 Correct 32 ms 104280 KB Output is correct
34 Correct 33 ms 104540 KB Output is correct
35 Correct 33 ms 104540 KB Output is correct
36 Correct 32 ms 104508 KB Output is correct
37 Correct 31 ms 104540 KB Output is correct
38 Correct 87 ms 108784 KB Output is correct
39 Correct 121 ms 153456 KB Output is correct
40 Correct 94 ms 108644 KB Output is correct
41 Correct 106 ms 108816 KB Output is correct
42 Correct 85 ms 108712 KB Output is correct
43 Correct 66 ms 108112 KB Output is correct
44 Correct 47 ms 105176 KB Output is correct
45 Correct 136 ms 143280 KB Output is correct
46 Correct 144 ms 143764 KB Output is correct
47 Correct 122 ms 148268 KB Output is correct
48 Correct 129 ms 148308 KB Output is correct
49 Correct 131 ms 143588 KB Output is correct
50 Correct 135 ms 143848 KB Output is correct
51 Correct 111 ms 144496 KB Output is correct
52 Correct 114 ms 144464 KB Output is correct
53 Correct 51 ms 110680 KB Output is correct
54 Correct 129 ms 143240 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 104284 KB Output is correct
2 Correct 22 ms 104256 KB Output is correct
3 Correct 22 ms 104240 KB Output is correct
4 Correct 20 ms 104284 KB Output is correct
5 Correct 385 ms 104444 KB Output is correct
6 Correct 31 ms 104540 KB Output is correct
7 Correct 28 ms 104284 KB Output is correct
8 Correct 28 ms 104284 KB Output is correct
9 Correct 28 ms 104280 KB Output is correct
10 Correct 29 ms 104448 KB Output is correct
11 Correct 32 ms 104284 KB Output is correct
12 Correct 30 ms 104528 KB Output is correct
13 Correct 426 ms 104440 KB Output is correct
14 Correct 505 ms 104756 KB Output is correct
15 Correct 425 ms 104508 KB Output is correct
16 Correct 250 ms 147028 KB Output is correct
17 Correct 582 ms 168592 KB Output is correct
18 Correct 1050 ms 202168 KB Output is correct
19 Correct 330 ms 153168 KB Output is correct
20 Correct 323 ms 152916 KB Output is correct
21 Correct 340 ms 153164 KB Output is correct
22 Correct 571 ms 167876 KB Output is correct
23 Correct 386 ms 167608 KB Output is correct
24 Correct 462 ms 167748 KB Output is correct
25 Correct 413 ms 167656 KB Output is correct
26 Correct 423 ms 168648 KB Output is correct
27 Correct 586 ms 177400 KB Output is correct
28 Correct 637 ms 180284 KB Output is correct
29 Correct 600 ms 174668 KB Output is correct
30 Correct 418 ms 162940 KB Output is correct
31 Correct 421 ms 164172 KB Output is correct
32 Correct 389 ms 162504 KB Output is correct
33 Correct 441 ms 164108 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 104284 KB Output is correct
2 Correct 22 ms 104376 KB Output is correct
3 Correct 20 ms 104284 KB Output is correct
4 Correct 222 ms 104468 KB Output is correct
5 Correct 446 ms 104480 KB Output is correct
6 Correct 30 ms 104280 KB Output is correct
7 Correct 32 ms 104284 KB Output is correct
8 Correct 31 ms 104536 KB Output is correct
9 Correct 84 ms 108680 KB Output is correct
10 Correct 127 ms 153940 KB Output is correct
11 Correct 464 ms 104448 KB Output is correct
12 Correct 495 ms 104844 KB Output is correct
13 Correct 251 ms 164692 KB Output is correct
14 Correct 248 ms 167096 KB Output is correct
15 Correct 557 ms 176720 KB Output is correct
16 Correct 1116 ms 214960 KB Output is correct
17 Correct 301 ms 182384 KB Output is correct
18 Correct 253 ms 176952 KB Output is correct
19 Correct 304 ms 178636 KB Output is correct
20 Correct 295 ms 178856 KB Output is correct
21 Correct 357 ms 181136 KB Output is correct
22 Correct 202 ms 163888 KB Output is correct
23 Correct 20 ms 104284 KB Output is correct
24 Correct 20 ms 104448 KB Output is correct
25 Correct 32 ms 104284 KB Output is correct
26 Correct 31 ms 104284 KB Output is correct
27 Correct 32 ms 104508 KB Output is correct
28 Correct 31 ms 104284 KB Output is correct
29 Correct 30 ms 104284 KB Output is correct
30 Correct 30 ms 104280 KB Output is correct
31 Correct 29 ms 104280 KB Output is correct
32 Correct 31 ms 104284 KB Output is correct
33 Correct 30 ms 104280 KB Output is correct
34 Correct 31 ms 104284 KB Output is correct
35 Correct 30 ms 104388 KB Output is correct
36 Correct 22 ms 104388 KB Output is correct
37 Correct 23 ms 104284 KB Output is correct
38 Correct 30 ms 104280 KB Output is correct
39 Correct 32 ms 104284 KB Output is correct
40 Correct 30 ms 104280 KB Output is correct
41 Correct 31 ms 104284 KB Output is correct
42 Correct 32 ms 104284 KB Output is correct
43 Correct 31 ms 104284 KB Output is correct
44 Correct 30 ms 104284 KB Output is correct
45 Correct 35 ms 104456 KB Output is correct
46 Correct 32 ms 104284 KB Output is correct
47 Correct 39 ms 104284 KB Output is correct
48 Correct 33 ms 104284 KB Output is correct
49 Correct 31 ms 104284 KB Output is correct
50 Correct 29 ms 104536 KB Output is correct
51 Correct 33 ms 104540 KB Output is correct
52 Correct 34 ms 104524 KB Output is correct
53 Correct 34 ms 104536 KB Output is correct
54 Correct 35 ms 104544 KB Output is correct
55 Correct 32 ms 104280 KB Output is correct
56 Correct 33 ms 104540 KB Output is correct
57 Correct 33 ms 104540 KB Output is correct
58 Correct 32 ms 104508 KB Output is correct
59 Correct 31 ms 104540 KB Output is correct
60 Correct 87 ms 108784 KB Output is correct
61 Correct 121 ms 153456 KB Output is correct
62 Correct 94 ms 108644 KB Output is correct
63 Correct 106 ms 108816 KB Output is correct
64 Correct 85 ms 108712 KB Output is correct
65 Correct 66 ms 108112 KB Output is correct
66 Correct 47 ms 105176 KB Output is correct
67 Correct 136 ms 143280 KB Output is correct
68 Correct 144 ms 143764 KB Output is correct
69 Correct 122 ms 148268 KB Output is correct
70 Correct 129 ms 148308 KB Output is correct
71 Correct 131 ms 143588 KB Output is correct
72 Correct 135 ms 143848 KB Output is correct
73 Correct 111 ms 144496 KB Output is correct
74 Correct 114 ms 144464 KB Output is correct
75 Correct 51 ms 110680 KB Output is correct
76 Correct 129 ms 143240 KB Output is correct
77 Correct 20 ms 104284 KB Output is correct
78 Correct 22 ms 104256 KB Output is correct
79 Correct 22 ms 104240 KB Output is correct
80 Correct 20 ms 104284 KB Output is correct
81 Correct 385 ms 104444 KB Output is correct
82 Correct 31 ms 104540 KB Output is correct
83 Correct 28 ms 104284 KB Output is correct
84 Correct 28 ms 104284 KB Output is correct
85 Correct 28 ms 104280 KB Output is correct
86 Correct 29 ms 104448 KB Output is correct
87 Correct 32 ms 104284 KB Output is correct
88 Correct 30 ms 104528 KB Output is correct
89 Correct 426 ms 104440 KB Output is correct
90 Correct 505 ms 104756 KB Output is correct
91 Correct 425 ms 104508 KB Output is correct
92 Correct 250 ms 147028 KB Output is correct
93 Correct 582 ms 168592 KB Output is correct
94 Correct 1050 ms 202168 KB Output is correct
95 Correct 330 ms 153168 KB Output is correct
96 Correct 323 ms 152916 KB Output is correct
97 Correct 340 ms 153164 KB Output is correct
98 Correct 571 ms 167876 KB Output is correct
99 Correct 386 ms 167608 KB Output is correct
100 Correct 462 ms 167748 KB Output is correct
101 Correct 413 ms 167656 KB Output is correct
102 Correct 423 ms 168648 KB Output is correct
103 Correct 586 ms 177400 KB Output is correct
104 Correct 637 ms 180284 KB Output is correct
105 Correct 600 ms 174668 KB Output is correct
106 Correct 418 ms 162940 KB Output is correct
107 Correct 421 ms 164172 KB Output is correct
108 Correct 389 ms 162504 KB Output is correct
109 Correct 441 ms 164108 KB Output is correct
110 Correct 401 ms 105976 KB Output is correct
111 Correct 313 ms 104976 KB Output is correct
112 Correct 703 ms 179628 KB Output is correct
113 Correct 328 ms 159060 KB Output is correct
114 Correct 561 ms 168312 KB Output is correct
115 Correct 141 ms 145356 KB Output is correct
116 Correct 372 ms 156712 KB Output is correct
117 Correct 1384 ms 220876 KB Output is correct
118 Correct 139 ms 144992 KB Output is correct
119 Correct 141 ms 145040 KB Output is correct
120 Correct 40 ms 111956 KB Output is correct
121 Correct 511 ms 159328 KB Output is correct
122 Correct 446 ms 159252 KB Output is correct
123 Correct 360 ms 162276 KB Output is correct
124 Correct 379 ms 162424 KB Output is correct
125 Correct 405 ms 163680 KB Output is correct
126 Correct 1134 ms 214676 KB Output is correct
127 Correct 507 ms 186136 KB Output is correct
128 Correct 386 ms 188840 KB Output is correct
129 Correct 400 ms 186012 KB Output is correct
130 Correct 394 ms 188028 KB Output is correct