oj.uz

답안 #648226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
648226 2022-10-05T18:05:00 Z victor_gao Jail (JOI22_jail) C++17
100 / 100
 2317 ms 632220 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 120015
#define C 21*120005
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,m,ac[25][N],have1[25][N],have2[25][N],in[N],out[N],dep[N],t=0,st[N],ed[N];
int after_st[N],after_ed[N];
int dfn[45*N],low[45*N],dft=0;
bool ins[45*N],ans=1;
stack<int>s;
vector<int>g[N],ng[45*N];
void dfs(int p,int lp){
    ac[0][p]=lp;
    in[p]=++t;
    dep[p]=dep[lp]+1;
    for (auto i:g[p]){
        if (i!=lp) dfs(i,p);
    }
    out[p]=++t;
}
int Hash(int u,int p,int i){
    return p*2*n+2*(u-1)+i;
}
void build(){
    out[0]=1e9; in[0]=0;
    for (int i=1;i<=19;i++){
        for (int j=1;j<=n;j++){
            ac[i][j]=ac[i-1][ac[i-1][j]];
            have1[i][j]=have1[i-1][j]+have1[i-1][ac[i-1][j]];
            if (have1[i-1][j]) ng[Hash(j,i-1,1)].push_back(Hash(j,i,1));
            if (have1[i-1][ac[i-1][j]]) ng[Hash(ac[i-1][j],i-1,1)].push_back(Hash(j,i,1));
            have2[i][j]=have2[i-1][j]+have2[i-1][ac[i-1][j]];
            if (have2[i-1][j]) ng[Hash(j,i,2)].push_back(Hash(j,i-1,2));
            if (have2[i-1][ac[i-1][j]]) ng[Hash(j,i,2)].push_back(Hash(ac[i-1][j],i-1,2));
        }
    }
}
bool check(int a,int b){
    return in[a]<=in[b]&&out[a]>=out[b];
}
int LCA(int a,int b){
    if (check(a,b)) return a;
    if (check(b,a)) return b;
    for (int i=19;i>=0;i--){
        if (!check(ac[i][a],b)) a=ac[i][a];
    }
    return ac[0][a];
}
void add(int u,int up,int is){
    if (up<=0){
        return;
    }
    int now=u;
    for (int i=19;i>=0;i--){ // 遇不同
        if (up&(1LL<<i)){
            if (is==1){
                ng[Hash(u,0,1)].push_back(Hash(now,i,2));
               // cout<<"add diff: "<<Hash(u,0,1)<<" "<<Hash(now,i,2)<<" "<<u<<' '<<now<<'\n';
            }
            else {
                ng[Hash(now,i,1)].push_back(Hash(u,0,2));
               // cout<<"add diff: "<<Hash(now,i,1)<<" "<<Hash(u,0,2)<<" "<<now<<" "<<u<<'\n';
            }
            now=ac[i][now];
        }
    }
    now=ac[0][u];
    for (int i=19;i>=0;i--){
        if (up&(1LL<<i)){
            if (is==1){
                ng[Hash(now,i,1)].push_back(Hash(u,0,1));
               // cout<<"add same: "<<Hash(now,i,1)<<" "<<Hash(u,0,1)<<'\n';
            }
            else {
                ng[Hash(u,0,2)].push_back(Hash(now,i,2));
              //  cout<<"add same: "<<Hash(u,0,2)<<" "<<Hash(now,i,2)<<'\n';
            }
            now=ac[i][now];
        }
    }
}
void tarjan(int p){
    dfn[p]=low[p]=++dft;
    s.push(p); ins[p]=1;
    for (auto i:ng[p]){
        if (!dfn[i]){
            tarjan(i);
            low[p]=min(low[p],low[i]);
        }
        else if (ins[i]&&dfn[i]<dfn[p])
            low[p]=min(low[p],dfn[i]);
    }
    if (low[p]==dfn[p]){
        int cnt=0;
        vector<int>cycle;
        for (int x=0;x!=p;s.pop()){
            x=s.top();
            cycle.push_back(x);
            ins[x]=0; cnt++;
        }
        if (cnt>2){
            ans=0;
            /*
            cout<<"Find : ";
            for (auto j:cycle)
                cout<<j<<" ";
            cout<<'\n';
            */
        } 
    }
}
void reset(){
    t=0; dft=0; ans=1;
    while (!s.empty()) s.pop();
    for (int i=0;i<=n+5;i++){
        g[i].clear();
        st[i]=0; ed[i]=0;
        after_st[i]=0; after_ed[i]=0;
        for (int j=0;j<=20;j++){
            have1[j][i]=0; have2[j][i]=0;
            ac[j][i]=0;
        }
    }
    for (int i=0;i<=42*n;i++){
        ins[i]=0; dfn[i]=0; low[i]=0;
        dep[i]=0; out[i]=0; in[i]=0;
        ng[i].clear();
    }
}
signed main(){
    fast
    int q; cin>>q;
    while (q--){
        cin>>n;
        reset();
        for (int i=1;i<n;i++){
            int a,b; cin>>a>>b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        cin>>m;
        for (int i=1;i<=m;i++){
            cin>>st[i]>>ed[i];
            have1[0][st[i]]=1;
            have2[0][ed[i]]=1;
            after_st[st[i]]=i;
            after_ed[ed[i]]=i;
        }
        dfs(1,1);
        build();
        /*
        for (int i=0;i<=5*n;i++){
            if (!ng[i].empty()){
                cout<<i<<" -> ";
                for (auto j:ng[i])
                    cout<<j<<" ";
                cout<<'\n';
            }
        }
        */
        for (int i=1;i<=m;i++){
            int a=st[i],b=ed[i];
            int lca=LCA(a,b);
            if (after_ed[lca]&&after_ed[lca]!=i)
                ng[Hash(a,0,1)].push_back(Hash(lca,0,2));
            if (after_st[lca]&&after_st[lca]!=i)
                ng[Hash(lca,0,1)].push_back(Hash(b,0,2));
            int dis=dep[a]-dep[lca];
            add(a,dis,1);
            dis=dep[b]-dep[lca];
            add(b,dis,2);
            ng[Hash(b,0,2)].push_back(Hash(a,0,1));
            ng[Hash(a,0,1)].push_back(Hash(b,0,2));
           // cout<<"add: "<<Hash(b,0,2)<<" "<<Hash(a,0,1)<<'\n';
        }
        /*
        for (int i=0;i<=5*n;i++){
            if (!ng[i].empty()){
                cout<<i<<" -> ";
                for (auto j:ng[i])
                    cout<<j<<" ";
                cout<<'\n';
            }
        }
        */
        for (int i=1;i<42*n;i++){
            if (!dfn[i]) tarjan(i);
        }
        if (ans) cout<<"Yes\n";
        else cout<<"No\n";
    }
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 130272 KB Output is correct
2 Correct 65 ms 130376 KB Output is correct
3 Correct 71 ms 130244 KB Output is correct
4 Correct 164 ms 130996 KB Output is correct
5 Correct 333 ms 131380 KB Output is correct
6 Correct 72 ms 130988 KB Output is correct
7 Correct 75 ms 130892 KB Output is correct
8 Correct 82 ms 131088 KB Output is correct
9 Correct 610 ms 146100 KB Output is correct
10 Correct 320 ms 233380 KB Output is correct
11 Correct 114 ms 130500 KB Output is correct
12 Correct 357 ms 131608 KB Output is correct
13 Correct 863 ms 363988 KB Output is correct
14 Correct 924 ms 371656 KB Output is correct
15 Correct 1611 ms 481252 KB Output is correct
16 Correct 2190 ms 632220 KB Output is correct
17 Correct 714 ms 303376 KB Output is correct
18 Correct 836 ms 368684 KB Output is correct
19 Correct 659 ms 314020 KB Output is correct
20 Correct 639 ms 313928 KB Output is correct
21 Correct 1427 ms 509036 KB Output is correct
22 Correct 923 ms 368608 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 130248 KB Output is correct
2 Correct 71 ms 130340 KB Output is correct
3 Correct 81 ms 130840 KB Output is correct
4 Correct 79 ms 130900 KB Output is correct
5 Correct 85 ms 130892 KB Output is correct
6 Correct 87 ms 130880 KB Output is correct
7 Correct 78 ms 130884 KB Output is correct
8 Correct 75 ms 130916 KB Output is correct
9 Correct 79 ms 130940 KB Output is correct
10 Correct 80 ms 130932 KB Output is correct
11 Correct 84 ms 131020 KB Output is correct
12 Correct 74 ms 130936 KB Output is correct
13 Correct 74 ms 130816 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 130248 KB Output is correct
2 Correct 71 ms 130340 KB Output is correct
3 Correct 81 ms 130840 KB Output is correct
4 Correct 79 ms 130900 KB Output is correct
5 Correct 85 ms 130892 KB Output is correct
6 Correct 87 ms 130880 KB Output is correct
7 Correct 78 ms 130884 KB Output is correct
8 Correct 75 ms 130916 KB Output is correct
9 Correct 79 ms 130940 KB Output is correct
10 Correct 80 ms 130932 KB Output is correct
11 Correct 84 ms 131020 KB Output is correct
12 Correct 74 ms 130936 KB Output is correct
13 Correct 74 ms 130816 KB Output is correct
14 Correct 70 ms 130308 KB Output is correct
15 Correct 70 ms 130276 KB Output is correct
16 Correct 83 ms 130956 KB Output is correct
17 Correct 82 ms 131016 KB Output is correct
18 Correct 75 ms 130968 KB Output is correct
19 Correct 74 ms 130388 KB Output is correct
20 Correct 82 ms 131072 KB Output is correct
21 Correct 87 ms 130940 KB Output is correct
22 Correct 86 ms 130832 KB Output is correct
23 Correct 66 ms 130352 KB Output is correct
24 Correct 72 ms 130480 KB Output is correct
25 Correct 87 ms 131020 KB Output is correct
26 Correct 75 ms 130568 KB Output is correct
27 Correct 74 ms 130872 KB Output is correct
28 Correct 70 ms 130372 KB Output is correct

Subtask #4
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 130248 KB Output is correct
2 Correct 71 ms 130340 KB Output is correct
3 Correct 81 ms 130840 KB Output is correct
4 Correct 79 ms 130900 KB Output is correct
5 Correct 85 ms 130892 KB Output is correct
6 Correct 87 ms 130880 KB Output is correct
7 Correct 78 ms 130884 KB Output is correct
8 Correct 75 ms 130916 KB Output is correct
9 Correct 79 ms 130940 KB Output is correct
10 Correct 80 ms 130932 KB Output is correct
11 Correct 84 ms 131020 KB Output is correct
12 Correct 74 ms 130936 KB Output is correct
13 Correct 74 ms 130816 KB Output is correct
14 Correct 70 ms 130308 KB Output is correct
15 Correct 70 ms 130276 KB Output is correct
16 Correct 83 ms 130956 KB Output is correct
17 Correct 82 ms 131016 KB Output is correct
18 Correct 75 ms 130968 KB Output is correct
19 Correct 74 ms 130388 KB Output is correct
20 Correct 82 ms 131072 KB Output is correct
21 Correct 87 ms 130940 KB Output is correct
22 Correct 86 ms 130832 KB Output is correct
23 Correct 66 ms 130352 KB Output is correct
24 Correct 72 ms 130480 KB Output is correct
25 Correct 87 ms 131020 KB Output is correct
26 Correct 75 ms 130568 KB Output is correct
27 Correct 74 ms 130872 KB Output is correct
28 Correct 70 ms 130372 KB Output is correct
29 Correct 84 ms 131068 KB Output is correct
30 Correct 85 ms 130984 KB Output is correct
31 Correct 78 ms 131096 KB Output is correct
32 Correct 88 ms 130908 KB Output is correct
33 Correct 87 ms 131072 KB Output is correct
34 Correct 92 ms 130784 KB Output is correct
35 Correct 81 ms 131000 KB Output is correct
36 Correct 82 ms 130940 KB Output is correct
37 Correct 76 ms 130808 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 130248 KB Output is correct
2 Correct 71 ms 130340 KB Output is correct
3 Correct 81 ms 130840 KB Output is correct
4 Correct 79 ms 130900 KB Output is correct
5 Correct 85 ms 130892 KB Output is correct
6 Correct 87 ms 130880 KB Output is correct
7 Correct 78 ms 130884 KB Output is correct
8 Correct 75 ms 130916 KB Output is correct
9 Correct 79 ms 130940 KB Output is correct
10 Correct 80 ms 130932 KB Output is correct
11 Correct 84 ms 131020 KB Output is correct
12 Correct 74 ms 130936 KB Output is correct
13 Correct 74 ms 130816 KB Output is correct
14 Correct 70 ms 130308 KB Output is correct
15 Correct 70 ms 130276 KB Output is correct
16 Correct 83 ms 130956 KB Output is correct
17 Correct 82 ms 131016 KB Output is correct
18 Correct 75 ms 130968 KB Output is correct
19 Correct 74 ms 130388 KB Output is correct
20 Correct 82 ms 131072 KB Output is correct
21 Correct 87 ms 130940 KB Output is correct
22 Correct 86 ms 130832 KB Output is correct
23 Correct 66 ms 130352 KB Output is correct
24 Correct 72 ms 130480 KB Output is correct
25 Correct 87 ms 131020 KB Output is correct
26 Correct 75 ms 130568 KB Output is correct
27 Correct 74 ms 130872 KB Output is correct
28 Correct 70 ms 130372 KB Output is correct
29 Correct 84 ms 131068 KB Output is correct
30 Correct 85 ms 130984 KB Output is correct
31 Correct 78 ms 131096 KB Output is correct
32 Correct 88 ms 130908 KB Output is correct
33 Correct 87 ms 131072 KB Output is correct
34 Correct 92 ms 130784 KB Output is correct
35 Correct 81 ms 131000 KB Output is correct
36 Correct 82 ms 130940 KB Output is correct
37 Correct 76 ms 130808 KB Output is correct
38 Correct 568 ms 146392 KB Output is correct
39 Correct 352 ms 233848 KB Output is correct
40 Correct 631 ms 146296 KB Output is correct
41 Correct 432 ms 144580 KB Output is correct
42 Correct 509 ms 145992 KB Output is correct
43 Correct 460 ms 144508 KB Output is correct
44 Correct 136 ms 132816 KB Output is correct
45 Correct 552 ms 241788 KB Output is correct
46 Correct 512 ms 238936 KB Output is correct
47 Correct 336 ms 217936 KB Output is correct
48 Correct 311 ms 217904 KB Output is correct
49 Correct 562 ms 255240 KB Output is correct
50 Correct 601 ms 249248 KB Output is correct
51 Correct 655 ms 291144 KB Output is correct
52 Correct 656 ms 299668 KB Output is correct
53 Correct 179 ms 145856 KB Output is correct
54 Correct 400 ms 218884 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 130284 KB Output is correct
2 Correct 70 ms 130520 KB Output is correct
3 Correct 68 ms 130268 KB Output is correct
4 Correct 84 ms 130288 KB Output is correct
5 Correct 113 ms 130488 KB Output is correct
6 Correct 72 ms 130880 KB Output is correct
7 Correct 80 ms 130884 KB Output is correct
8 Correct 80 ms 130280 KB Output is correct
9 Correct 71 ms 130336 KB Output is correct
10 Correct 70 ms 130652 KB Output is correct
11 Correct 72 ms 130292 KB Output is correct
12 Correct 75 ms 130924 KB Output is correct
13 Correct 235 ms 131332 KB Output is correct
14 Correct 339 ms 131608 KB Output is correct
15 Correct 287 ms 131368 KB Output is correct
16 Correct 749 ms 275676 KB Output is correct
17 Correct 1579 ms 372184 KB Output is correct
18 Correct 1434 ms 432060 KB Output is correct
19 Correct 631 ms 240364 KB Output is correct
20 Correct 728 ms 251512 KB Output is correct
21 Correct 658 ms 244652 KB Output is correct
22 Correct 794 ms 334220 KB Output is correct
23 Correct 820 ms 330568 KB Output is correct
24 Correct 794 ms 328360 KB Output is correct
25 Correct 822 ms 328280 KB Output is correct
26 Correct 845 ms 328360 KB Output is correct
27 Correct 1158 ms 378604 KB Output is correct
28 Correct 1092 ms 403888 KB Output is correct
29 Correct 1116 ms 387076 KB Output is correct
30 Correct 1257 ms 340208 KB Output is correct
31 Correct 1214 ms 352484 KB Output is correct
32 Correct 894 ms 343196 KB Output is correct
33 Correct 902 ms 355460 KB Output is correct

Subtask #7
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 130272 KB Output is correct
2 Correct 65 ms 130376 KB Output is correct
3 Correct 71 ms 130244 KB Output is correct
4 Correct 164 ms 130996 KB Output is correct
5 Correct 333 ms 131380 KB Output is correct
6 Correct 72 ms 130988 KB Output is correct
7 Correct 75 ms 130892 KB Output is correct
8 Correct 82 ms 131088 KB Output is correct
9 Correct 610 ms 146100 KB Output is correct
10 Correct 320 ms 233380 KB Output is correct
11 Correct 114 ms 130500 KB Output is correct
12 Correct 357 ms 131608 KB Output is correct
13 Correct 863 ms 363988 KB Output is correct
14 Correct 924 ms 371656 KB Output is correct
15 Correct 1611 ms 481252 KB Output is correct
16 Correct 2190 ms 632220 KB Output is correct
17 Correct 714 ms 303376 KB Output is correct
18 Correct 836 ms 368684 KB Output is correct
19 Correct 659 ms 314020 KB Output is correct
20 Correct 639 ms 313928 KB Output is correct
21 Correct 1427 ms 509036 KB Output is correct
22 Correct 923 ms 368608 KB Output is correct
23 Correct 78 ms 130248 KB Output is correct
24 Correct 71 ms 130340 KB Output is correct
25 Correct 81 ms 130840 KB Output is correct
26 Correct 79 ms 130900 KB Output is correct
27 Correct 85 ms 130892 KB Output is correct
28 Correct 87 ms 130880 KB Output is correct
29 Correct 78 ms 130884 KB Output is correct
30 Correct 75 ms 130916 KB Output is correct
31 Correct 79 ms 130940 KB Output is correct
32 Correct 80 ms 130932 KB Output is correct
33 Correct 84 ms 131020 KB Output is correct
34 Correct 74 ms 130936 KB Output is correct
35 Correct 74 ms 130816 KB Output is correct
36 Correct 70 ms 130308 KB Output is correct
37 Correct 70 ms 130276 KB Output is correct
38 Correct 83 ms 130956 KB Output is correct
39 Correct 82 ms 131016 KB Output is correct
40 Correct 75 ms 130968 KB Output is correct
41 Correct 74 ms 130388 KB Output is correct
42 Correct 82 ms 131072 KB Output is correct
43 Correct 87 ms 130940 KB Output is correct
44 Correct 86 ms 130832 KB Output is correct
45 Correct 66 ms 130352 KB Output is correct
46 Correct 72 ms 130480 KB Output is correct
47 Correct 87 ms 131020 KB Output is correct
48 Correct 75 ms 130568 KB Output is correct
49 Correct 74 ms 130872 KB Output is correct
50 Correct 70 ms 130372 KB Output is correct
51 Correct 84 ms 131068 KB Output is correct
52 Correct 85 ms 130984 KB Output is correct
53 Correct 78 ms 131096 KB Output is correct
54 Correct 88 ms 130908 KB Output is correct
55 Correct 87 ms 131072 KB Output is correct
56 Correct 92 ms 130784 KB Output is correct
57 Correct 81 ms 131000 KB Output is correct
58 Correct 82 ms 130940 KB Output is correct
59 Correct 76 ms 130808 KB Output is correct
60 Correct 568 ms 146392 KB Output is correct
61 Correct 352 ms 233848 KB Output is correct
62 Correct 631 ms 146296 KB Output is correct
63 Correct 432 ms 144580 KB Output is correct
64 Correct 509 ms 145992 KB Output is correct
65 Correct 460 ms 144508 KB Output is correct
66 Correct 136 ms 132816 KB Output is correct
67 Correct 552 ms 241788 KB Output is correct
68 Correct 512 ms 238936 KB Output is correct
69 Correct 336 ms 217936 KB Output is correct
70 Correct 311 ms 217904 KB Output is correct
71 Correct 562 ms 255240 KB Output is correct
72 Correct 601 ms 249248 KB Output is correct
73 Correct 655 ms 291144 KB Output is correct
74 Correct 656 ms 299668 KB Output is correct
75 Correct 179 ms 145856 KB Output is correct
76 Correct 400 ms 218884 KB Output is correct
77 Correct 69 ms 130284 KB Output is correct
78 Correct 70 ms 130520 KB Output is correct
79 Correct 68 ms 130268 KB Output is correct
80 Correct 84 ms 130288 KB Output is correct
81 Correct 113 ms 130488 KB Output is correct
82 Correct 72 ms 130880 KB Output is correct
83 Correct 80 ms 130884 KB Output is correct
84 Correct 80 ms 130280 KB Output is correct
85 Correct 71 ms 130336 KB Output is correct
86 Correct 70 ms 130652 KB Output is correct
87 Correct 72 ms 130292 KB Output is correct
88 Correct 75 ms 130924 KB Output is correct
89 Correct 235 ms 131332 KB Output is correct
90 Correct 339 ms 131608 KB Output is correct
91 Correct 287 ms 131368 KB Output is correct
92 Correct 749 ms 275676 KB Output is correct
93 Correct 1579 ms 372184 KB Output is correct
94 Correct 1434 ms 432060 KB Output is correct
95 Correct 631 ms 240364 KB Output is correct
96 Correct 728 ms 251512 KB Output is correct
97 Correct 658 ms 244652 KB Output is correct
98 Correct 794 ms 334220 KB Output is correct
99 Correct 820 ms 330568 KB Output is correct
100 Correct 794 ms 328360 KB Output is correct
101 Correct 822 ms 328280 KB Output is correct
102 Correct 845 ms 328360 KB Output is correct
103 Correct 1158 ms 378604 KB Output is correct
104 Correct 1092 ms 403888 KB Output is correct
105 Correct 1116 ms 387076 KB Output is correct
106 Correct 1257 ms 340208 KB Output is correct
107 Correct 1214 ms 352484 KB Output is correct
108 Correct 894 ms 343196 KB Output is correct
109 Correct 902 ms 355460 KB Output is correct
110 Correct 380 ms 131940 KB Output is correct
111 Correct 262 ms 131344 KB Output is correct
112 Correct 1846 ms 481328 KB Output is correct
113 Correct 640 ms 247008 KB Output is correct
114 Correct 1488 ms 438920 KB Output is correct
115 Correct 579 ms 289032 KB Output is correct
116 Correct 1207 ms 326416 KB Output is correct
117 Correct 1587 ms 448508 KB Output is correct
118 Correct 449 ms 225444 KB Output is correct
119 Correct 436 ms 226576 KB Output is correct
120 Correct 157 ms 148960 KB Output is correct
121 Correct 1100 ms 358792 KB Output is correct
122 Correct 1237 ms 327964 KB Output is correct
123 Correct 796 ms 280568 KB Output is correct
124 Correct 1213 ms 330684 KB Output is correct
125 Correct 775 ms 258368 KB Output is correct
126 Correct 2317 ms 613504 KB Output is correct
127 Correct 1057 ms 455196 KB Output is correct
128 Correct 919 ms 409716 KB Output is correct
129 Correct 896 ms 383988 KB Output is correct
130 Correct 956 ms 442812 KB Output is correct