oj.uz

Submission #1110336

# Submission time Handle Problem Language Result Execution time Memory
1110336 2024-11-09T09:26:03 Z 8pete8 Jail (JOI22_jail) C++17
77 / 100
 5000 ms 127164 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5+5,inf=1e18,minf=-1e18,lg=30;
//#undef int
int n,k,m;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
vector<int>adj[mxn+10];
int S[mxn+10],T[mxn+10],target,root;
int hvyp[mxn+10],sz[mxn+10],tin[mxn+10],tout[mxn+10],up[mxn+10][lg+1],h[mxn+10];
pii tmp;
struct segmx{
    pii v[2*mxn+10];
    priority_queue<pii>pq[mxn+10];
    void init(){for(int i=0;i<=2*n;i++)v[i]={minf,minf};}
    void update(int pos,pii val,int del){
        if(!del)pq[pos].push(val);
        else{
            if(pq[pos].top()==val)pq[pos].pop();
            else{
                tmp=pq[pos].top();
                pq[pos].pop();
                pq[pos].pop();
                pq[pos].push(tmp);
            }
        }
        if(!pq[pos].empty())v[pos+n]=pq[pos].top();
        else v[pos+n]={minf,minf};
        pos+=n;
        for(int i=pos;i>0;i>>=1)v[i>>1]=max(v[i],v[i^1]);
    }
    pii qry(int l,int r){
        pii ans={minf,minf};
        for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
            if(l&1)ans=max(ans,v[l++]);
            if(!(r&1))ans=max(ans,v[r--]);
        }
        return ans;
    }
}t;
struct segmn{
    pii v[2*mxn+10];
    priority_queue<pii,vector<pii>,greater<pii>>pq[mxn+10];
    void init(){for(int i=0;i<=2*n;i++)v[i]={inf,inf};}
    void update(int pos,pii val,int del){
        if(!del)pq[pos].push(val);
        else{
            if(pq[pos].top()==val)pq[pos].pop();
            else{
                tmp=pq[pos].top();
                pq[pos].pop();
                pq[pos].pop();
                pq[pos].push(tmp);
            }
        }
        if(!pq[pos].empty())v[pos+n]=pq[pos].top();
        else v[pos+n]={inf,inf};
        pos+=n;
        for(int i=pos;i>0;i>>=1)v[i>>1]=min(v[i],v[i^1]);
    }
    pii qry(int l,int r){
        pii ans={inf,inf};
        for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
            if(l&1)ans=min(ans,v[l++]);
            if(!(r&1))ans=min(ans,v[r--]);
        }
        return ans;
    }
}t2,t3;
int ct=0;
int lca(int x,int y){
    if(h[x]<h[y])swap(x,y);
    int k=h[x]-h[y];
    for(int i=0;i<=lg;i++)if(k&(1LL<<i))x=up[x][i];
    if(x==y)return x;
    for(int i=lg;i>=0;i--)if(up[x][i]!=up[y][i]){
        x=up[x][i],y=up[y][i];
    }
    return up[x][0];
}
void getsz(int cur,int p){sz[cur]=1;for(auto i:adj[cur])if(i!=p)getsz(i,cur),sz[cur]+=i;}
void dfs(int cur,int p){
    sz[cur]=1;
    tin[cur]=++ct;
    int hvy=0;
    for(auto i:adj[cur])if(i!=p&&sz[i]>sz[hvy])hvy=i;
    if(hvy){
        hvyp[hvy]=hvyp[cur];
        up[hvy][0]=cur,h[hvy]=h[cur]+1;
        sz[cur]+=sz[hvy];
        dfs(hvy,cur);
    }
    for(auto i:adj[cur])if(i!=p&&i!=hvy){
        up[i][0]=cur;
        h[i]=h[cur]+1;
        hvyp[i]=i;
        dfs(i,cur),sz[cur]+=sz[i];
    }
    tout[cur]=ct;
}
int on[mxn+10],vis[mxn+10];
void del(int i){
    t.update(tin[S[i]],{tin[T[i]],i},1);
    t.update(tin[T[i]],{tin[S[i]],i},1);
    t2.update(tin[S[i]],{tin[T[i]],i},1);
    t2.update(tin[T[i]],{tin[S[i]],i},1);
    t3.update(tin[T[i]],{i,i},1);
}
bool findcycle(int cur){
    if(on[cur])return 1;
    if(vis[cur])return 0;
    vis[cur]=on[cur]=1;
    pii go={inf,inf};
    int x=0;
    while(x<adj[S[cur]].size()){
        if(adj[S[cur]][x]==up[S[cur]][0]){
            x++;
            continue;
        }
        t.update(tin[T[cur]],{tin[S[cur]],cur},1);
        go=t.qry(tin[adj[S[cur]][x]],tout[adj[S[cur]][x]]);
        t.update(tin[T[cur]],{tin[S[cur]],cur},0);
       
        if(go.f!=inf&&go.f!=minf&&go.f>tout[adj[S[cur]][x]]){
            if(findcycle(go.s))return 1;
        }
        else x++;
    }
    x=0;
    while(x<adj[S[cur]].size()){
        if(adj[S[cur]][x]==up[S[cur]][0]){
            x++;
            continue;
        }
        t2.update(tin[T[cur]],{tin[S[cur]],cur},1);
        go=t2.qry(tin[adj[S[cur]][x]],tout[adj[S[cur]][x]]);
        t2.update(tin[T[cur]],{tin[S[cur]],cur},0);
        if(go.f!=inf&&go.f!=minf&&go.f<tin[adj[S[cur]][x]]){
            if(findcycle(go.s))return 1;
        }
        else x++;
    }
    int curhvy=S[cur],node=lca(S[cur],T[cur]);
    while(hvyp[curhvy]!=hvyp[node]){
        t3.update(tin[T[cur]],{cur,cur},1);
        go=t3.qry(tin[hvyp[curhvy]],tin[curhvy]);
        t3.update(tin[T[cur]],{cur,cur},0);
        if(go.f!=inf&&go.f!=minf){
            if(findcycle(go.s))return 1;
        }
        else curhvy=up[hvyp[curhvy]][0];
    }
    while(1){
        t3.update(tin[T[cur]],{cur,cur},1);
        go=t3.qry(tin[node],tin[curhvy]);
        t3.update(tin[T[cur]],{cur,cur},0);
        if(go.f!=inf&&go.f!=minf){
            if(findcycle(go.s))return 1;
        }
        else break;
    }
    curhvy=T[cur];
    while(hvyp[curhvy]!=hvyp[node]){
        t3.update(tin[T[cur]],{cur,cur},1);
        go=t3.qry(tin[hvyp[curhvy]],tin[curhvy]);
        t3.update(tin[T[cur]],{cur,cur},0);
        if(go.f!=inf&&go.f!=minf){
            if(findcycle(go.s))return 1;
        }
        else curhvy=up[hvyp[curhvy]][0];
    }
    while(1){
        t3.update(tin[T[cur]],{cur,cur},1);
        go=t3.qry(tin[node],tin[curhvy]);
        t3.update(tin[T[cur]],{cur,cur},0);
        if(go.f!=inf&&go.f!=minf){
            if(findcycle(go.s))return 1;
        }
        else break;
    }
    del(cur);
    on[cur]=0;
    return 0;
}
void solve(){
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    ct=0;
    cin>>m;
    for(int i=1;i<=m;i++)cin>>S[i]>>T[i];
    hvyp[1]=1;
    t.init();
    t2.init();
    t3.init();
    getsz(1,-1);
    dfs(1,-1);
    for(int i=1;i<=m;i++){
        t.update(tin[S[i]],{tin[T[i]],i},0);
        t.update(tin[T[i]],{tin[S[i]],i},0);
        t2.update(tin[S[i]],{tin[T[i]],i},0);
        t2.update(tin[T[i]],{tin[S[i]],i},0);
        t3.update(tin[T[i]],{i,i},0);
    }
    for(int j=0;j<=lg;j++)up[1][j]=1;
    for(int j=1;j<=lg;j++)for(int i=1;i<=n;i++)up[i][j]=up[up[i][j-1]][j-1];
    bool yes=0;
    for(int i=1;i<=m;i++)if(!vis[i]){
        yes|=findcycle(i);
    }
    if(yes)cout<<"No\n";
    else cout<<"Yes\n";
    for(int i=1;i<=n;i++){
        adj[i].clear(),on[i]=vis[i]=S[i]=T[i]=vis[i]=0;
        while(!t.pq[i].empty())t.pq[i].pop();
        while(!t2.pq[i].empty())t2.pq[i].pop();
        while(!t3.pq[i].empty())t3.pq[i].pop();
    }
}
int32_t main(){
    fastio
    int t;cin>>t;
    while(t--)solve();
}
/*
let say the end point of prisoneri is on the path of prisonerj
then j has to move before i
j->i
if the start point of prisoner i is on the path of prisoner j
then i has to move before j
i->j
we can build a dag then see if theres a cycle

when dfs in dag to check for cycle a node is visited only once
we dont need to build the whole graph
just dfs and slowly check for adjacent node
if the adjacent node is not on the current path then just continue dfs
else if its on we found a cycle

after each dfs we can delete all visited node from the graph
will only use O(n*getnxt())
getnxt : 
find all prisoner that pass the start node->how??{
    segtree on euler tour
    keep the counter part tin time
    when qry (l,r) just need to check if theres a node outside the range (l,r)
}
find all prisoner that has end point on path (start,end)->hld
*/

Compilation message

jail.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
jail.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void setIO(string name){
      |                       ^
jail.cpp:50:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   50 |     void init(){for(int i=0;i<=2*n;i++)v[i]={minf,minf};}
      |               ^
jail.cpp:51:40: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   51 |     void update(int pos,pii val,int del){
      |                                        ^
jail.cpp:67:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   67 |     pii qry(int l,int r){
      |                        ^
jail.cpp:79:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   79 |     void init(){for(int i=0;i<=2*n;i++)v[i]={inf,inf};}
      |               ^
jail.cpp:80:40: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   80 |     void update(int pos,pii val,int del){
      |                                        ^
jail.cpp:96:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   96 |     pii qry(int l,int r){
      |                        ^
jail.cpp:106:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  106 | int lca(int x,int y){
      |                    ^
jail.cpp:116:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  116 | void getsz(int cur,int p){sz[cur]=1;for(auto i:adj[cur])if(i!=p)getsz(i,cur),sz[cur]+=i;}
      |                         ^
jail.cpp:117:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  117 | void dfs(int cur,int p){
      |                       ^
jail.cpp:137:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  137 | void del(int i){
      |               ^
jail.cpp:144:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  144 | bool findcycle(int cur){
      |                       ^
jail.cpp: In function 'bool findcycle(long long int)':
jail.cpp:150:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     while(x<adj[S[cur]].size()){
      |           ~^~~~~~~~~~~~~~~~~~~
jail.cpp:165:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |     while(x<adj[S[cur]].size()){
      |           ~^~~~~~~~~~~~~~~~~~~
jail.cpp: At global scope:
jail.cpp:220:12: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  220 | void solve(){
      |            ^
jail.cpp: In function 'void solve()':
jail.cpp:252:36: warning: operation on 'vis[i]' may be undefined [-Wsequence-point]
  252 |         adj[i].clear(),on[i]=vis[i]=S[i]=T[i]=vis[i]=0;
      |                              ~~~~~~^~~~~~~~~~~~~~~~~~~
jail.cpp: At global scope:
jail.cpp:258:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  258 | int32_t main(){
      |              ^
jail.cpp: In function 'void setIO(std::string)':
jail.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 55888 KB Output is correct
2 Correct 7 ms 55888 KB Output is correct
3 Correct 7 ms 55888 KB Output is correct
4 Correct 15 ms 56312 KB Output is correct
5 Correct 28 ms 56656 KB Output is correct
6 Correct 8 ms 55888 KB Output is correct
7 Correct 8 ms 55888 KB Output is correct
8 Correct 12 ms 55888 KB Output is correct
9 Correct 50 ms 60232 KB Output is correct
10 Correct 56 ms 100660 KB Output is correct
11 Correct 15 ms 55888 KB Output is correct
12 Correct 56 ms 56852 KB Output is correct
13 Correct 156 ms 107088 KB Output is correct
14 Correct 131 ms 109120 KB Output is correct
15 Correct 187 ms 108444 KB Output is correct
16 Correct 375 ms 118816 KB Output is correct
17 Correct 187 ms 110924 KB Output is correct
18 Correct 288 ms 117284 KB Output is correct
19 Correct 190 ms 110920 KB Output is correct
20 Correct 171 ms 110712 KB Output is correct
21 Correct 150 ms 110792 KB Output is correct
22 Correct 143 ms 110920 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 56056 KB Output is correct
2 Correct 8 ms 55888 KB Output is correct
3 Correct 9 ms 55888 KB Output is correct
4 Correct 10 ms 55888 KB Output is correct
5 Correct 9 ms 56016 KB Output is correct
6 Correct 9 ms 55888 KB Output is correct
7 Correct 9 ms 55888 KB Output is correct
8 Correct 9 ms 55888 KB Output is correct
9 Correct 9 ms 55888 KB Output is correct
10 Correct 10 ms 55888 KB Output is correct
11 Correct 9 ms 55888 KB Output is correct
12 Correct 9 ms 55888 KB Output is correct
13 Correct 9 ms 55888 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 56056 KB Output is correct
2 Correct 8 ms 55888 KB Output is correct
3 Correct 9 ms 55888 KB Output is correct
4 Correct 10 ms 55888 KB Output is correct
5 Correct 9 ms 56016 KB Output is correct
6 Correct 9 ms 55888 KB Output is correct
7 Correct 9 ms 55888 KB Output is correct
8 Correct 9 ms 55888 KB Output is correct
9 Correct 9 ms 55888 KB Output is correct
10 Correct 10 ms 55888 KB Output is correct
11 Correct 9 ms 55888 KB Output is correct
12 Correct 9 ms 55888 KB Output is correct
13 Correct 9 ms 55888 KB Output is correct
14 Correct 8 ms 55888 KB Output is correct
15 Correct 8 ms 55888 KB Output is correct
16 Correct 9 ms 55888 KB Output is correct
17 Correct 9 ms 55972 KB Output is correct
18 Correct 10 ms 55888 KB Output is correct
19 Correct 8 ms 55888 KB Output is correct
20 Correct 9 ms 56144 KB Output is correct
21 Correct 10 ms 56056 KB Output is correct
22 Correct 9 ms 55888 KB Output is correct
23 Correct 8 ms 55888 KB Output is correct
24 Correct 8 ms 55888 KB Output is correct
25 Correct 11 ms 55888 KB Output is correct
26 Correct 8 ms 55900 KB Output is correct
27 Correct 9 ms 55944 KB Output is correct
28 Correct 8 ms 56060 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 56056 KB Output is correct
2 Correct 8 ms 55888 KB Output is correct
3 Correct 9 ms 55888 KB Output is correct
4 Correct 10 ms 55888 KB Output is correct
5 Correct 9 ms 56016 KB Output is correct
6 Correct 9 ms 55888 KB Output is correct
7 Correct 9 ms 55888 KB Output is correct
8 Correct 9 ms 55888 KB Output is correct
9 Correct 9 ms 55888 KB Output is correct
10 Correct 10 ms 55888 KB Output is correct
11 Correct 9 ms 55888 KB Output is correct
12 Correct 9 ms 55888 KB Output is correct
13 Correct 9 ms 55888 KB Output is correct
14 Correct 8 ms 55888 KB Output is correct
15 Correct 8 ms 55888 KB Output is correct
16 Correct 9 ms 55888 KB Output is correct
17 Correct 9 ms 55972 KB Output is correct
18 Correct 10 ms 55888 KB Output is correct
19 Correct 8 ms 55888 KB Output is correct
20 Correct 9 ms 56144 KB Output is correct
21 Correct 10 ms 56056 KB Output is correct
22 Correct 9 ms 55888 KB Output is correct
23 Correct 8 ms 55888 KB Output is correct
24 Correct 8 ms 55888 KB Output is correct
25 Correct 11 ms 55888 KB Output is correct
26 Correct 8 ms 55900 KB Output is correct
27 Correct 9 ms 55944 KB Output is correct
28 Correct 8 ms 56060 KB Output is correct
29 Correct 11 ms 55888 KB Output is correct
30 Correct 11 ms 55864 KB Output is correct
31 Correct 10 ms 55888 KB Output is correct
32 Correct 12 ms 55888 KB Output is correct
33 Correct 10 ms 55888 KB Output is correct
34 Correct 12 ms 56040 KB Output is correct
35 Correct 12 ms 55900 KB Output is correct
36 Correct 11 ms 55888 KB Output is correct
37 Correct 10 ms 55888 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 56056 KB Output is correct
2 Correct 8 ms 55888 KB Output is correct
3 Correct 9 ms 55888 KB Output is correct
4 Correct 10 ms 55888 KB Output is correct
5 Correct 9 ms 56016 KB Output is correct
6 Correct 9 ms 55888 KB Output is correct
7 Correct 9 ms 55888 KB Output is correct
8 Correct 9 ms 55888 KB Output is correct
9 Correct 9 ms 55888 KB Output is correct
10 Correct 10 ms 55888 KB Output is correct
11 Correct 9 ms 55888 KB Output is correct
12 Correct 9 ms 55888 KB Output is correct
13 Correct 9 ms 55888 KB Output is correct
14 Correct 8 ms 55888 KB Output is correct
15 Correct 8 ms 55888 KB Output is correct
16 Correct 9 ms 55888 KB Output is correct
17 Correct 9 ms 55972 KB Output is correct
18 Correct 10 ms 55888 KB Output is correct
19 Correct 8 ms 55888 KB Output is correct
20 Correct 9 ms 56144 KB Output is correct
21 Correct 10 ms 56056 KB Output is correct
22 Correct 9 ms 55888 KB Output is correct
23 Correct 8 ms 55888 KB Output is correct
24 Correct 8 ms 55888 KB Output is correct
25 Correct 11 ms 55888 KB Output is correct
26 Correct 8 ms 55900 KB Output is correct
27 Correct 9 ms 55944 KB Output is correct
28 Correct 8 ms 56060 KB Output is correct
29 Correct 11 ms 55888 KB Output is correct
30 Correct 11 ms 55864 KB Output is correct
31 Correct 10 ms 55888 KB Output is correct
32 Correct 12 ms 55888 KB Output is correct
33 Correct 10 ms 55888 KB Output is correct
34 Correct 12 ms 56040 KB Output is correct
35 Correct 12 ms 55900 KB Output is correct
36 Correct 11 ms 55888 KB Output is correct
37 Correct 10 ms 55888 KB Output is correct
38 Correct 54 ms 60500 KB Output is correct
39 Correct 66 ms 100180 KB Output is correct
40 Correct 60 ms 58956 KB Output is correct
41 Correct 71 ms 60152 KB Output is correct
42 Correct 55 ms 59468 KB Output is correct
43 Correct 45 ms 59464 KB Output is correct
44 Correct 31 ms 56144 KB Output is correct
45 Correct 91 ms 89936 KB Output is correct
46 Correct 79 ms 91992 KB Output is correct
47 Correct 166 ms 96840 KB Output is correct
48 Correct 167 ms 96680 KB Output is correct
49 Correct 73 ms 92232 KB Output is correct
50 Correct 82 ms 92224 KB Output is correct
51 Correct 55 ms 93512 KB Output is correct
52 Correct 57 ms 93384 KB Output is correct
53 Correct 29 ms 58888 KB Output is correct
54 Correct 79 ms 92504 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 55888 KB Output is correct
2 Correct 8 ms 55888 KB Output is correct
3 Correct 9 ms 56056 KB Output is correct
4 Correct 8 ms 55888 KB Output is correct
5 Correct 16 ms 55900 KB Output is correct
6 Correct 8 ms 56060 KB Output is correct
7 Correct 8 ms 55948 KB Output is correct
8 Correct 8 ms 55888 KB Output is correct
9 Correct 8 ms 55888 KB Output is correct
10 Correct 8 ms 55860 KB Output is correct
11 Correct 8 ms 55888 KB Output is correct
12 Correct 11 ms 55888 KB Output is correct
13 Correct 37 ms 56392 KB Output is correct
14 Correct 67 ms 55888 KB Output is correct
15 Correct 56 ms 56716 KB Output is correct
16 Correct 128 ms 93256 KB Output is correct
17 Correct 232 ms 101448 KB Output is correct
18 Correct 352 ms 110204 KB Output is correct
19 Correct 171 ms 95304 KB Output is correct
20 Correct 168 ms 95304 KB Output is correct
21 Correct 176 ms 95540 KB Output is correct
22 Correct 260 ms 102224 KB Output is correct
23 Correct 202 ms 102216 KB Output is correct
24 Correct 334 ms 102216 KB Output is correct
25 Correct 333 ms 102216 KB Output is correct
26 Correct 378 ms 102216 KB Output is correct
27 Correct 657 ms 114584 KB Output is correct
28 Correct 399 ms 127164 KB Output is correct
29 Correct 366 ms 118112 KB Output is correct
30 Correct 380 ms 108736 KB Output is correct
31 Correct 223 ms 110272 KB Output is correct
32 Correct 402 ms 106432 KB Output is correct
33 Correct 219 ms 110360 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 55888 KB Output is correct
2 Correct 7 ms 55888 KB Output is correct
3 Correct 7 ms 55888 KB Output is correct
4 Correct 15 ms 56312 KB Output is correct
5 Correct 28 ms 56656 KB Output is correct
6 Correct 8 ms 55888 KB Output is correct
7 Correct 8 ms 55888 KB Output is correct
8 Correct 12 ms 55888 KB Output is correct
9 Correct 50 ms 60232 KB Output is correct
10 Correct 56 ms 100660 KB Output is correct
11 Correct 15 ms 55888 KB Output is correct
12 Correct 56 ms 56852 KB Output is correct
13 Correct 156 ms 107088 KB Output is correct
14 Correct 131 ms 109120 KB Output is correct
15 Correct 187 ms 108444 KB Output is correct
16 Correct 375 ms 118816 KB Output is correct
17 Correct 187 ms 110924 KB Output is correct
18 Correct 288 ms 117284 KB Output is correct
19 Correct 190 ms 110920 KB Output is correct
20 Correct 171 ms 110712 KB Output is correct
21 Correct 150 ms 110792 KB Output is correct
22 Correct 143 ms 110920 KB Output is correct
23 Correct 8 ms 56056 KB Output is correct
24 Correct 8 ms 55888 KB Output is correct
25 Correct 9 ms 55888 KB Output is correct
26 Correct 10 ms 55888 KB Output is correct
27 Correct 9 ms 56016 KB Output is correct
28 Correct 9 ms 55888 KB Output is correct
29 Correct 9 ms 55888 KB Output is correct
30 Correct 9 ms 55888 KB Output is correct
31 Correct 9 ms 55888 KB Output is correct
32 Correct 10 ms 55888 KB Output is correct
33 Correct 9 ms 55888 KB Output is correct
34 Correct 9 ms 55888 KB Output is correct
35 Correct 9 ms 55888 KB Output is correct
36 Correct 8 ms 55888 KB Output is correct
37 Correct 8 ms 55888 KB Output is correct
38 Correct 9 ms 55888 KB Output is correct
39 Correct 9 ms 55972 KB Output is correct
40 Correct 10 ms 55888 KB Output is correct
41 Correct 8 ms 55888 KB Output is correct
42 Correct 9 ms 56144 KB Output is correct
43 Correct 10 ms 56056 KB Output is correct
44 Correct 9 ms 55888 KB Output is correct
45 Correct 8 ms 55888 KB Output is correct
46 Correct 8 ms 55888 KB Output is correct
47 Correct 11 ms 55888 KB Output is correct
48 Correct 8 ms 55900 KB Output is correct
49 Correct 9 ms 55944 KB Output is correct
50 Correct 8 ms 56060 KB Output is correct
51 Correct 11 ms 55888 KB Output is correct
52 Correct 11 ms 55864 KB Output is correct
53 Correct 10 ms 55888 KB Output is correct
54 Correct 12 ms 55888 KB Output is correct
55 Correct 10 ms 55888 KB Output is correct
56 Correct 12 ms 56040 KB Output is correct
57 Correct 12 ms 55900 KB Output is correct
58 Correct 11 ms 55888 KB Output is correct
59 Correct 10 ms 55888 KB Output is correct
60 Correct 54 ms 60500 KB Output is correct
61 Correct 66 ms 100180 KB Output is correct
62 Correct 60 ms 58956 KB Output is correct
63 Correct 71 ms 60152 KB Output is correct
64 Correct 55 ms 59468 KB Output is correct
65 Correct 45 ms 59464 KB Output is correct
66 Correct 31 ms 56144 KB Output is correct
67 Correct 91 ms 89936 KB Output is correct
68 Correct 79 ms 91992 KB Output is correct
69 Correct 166 ms 96840 KB Output is correct
70 Correct 167 ms 96680 KB Output is correct
71 Correct 73 ms 92232 KB Output is correct
72 Correct 82 ms 92224 KB Output is correct
73 Correct 55 ms 93512 KB Output is correct
74 Correct 57 ms 93384 KB Output is correct
75 Correct 29 ms 58888 KB Output is correct
76 Correct 79 ms 92504 KB Output is correct
77 Correct 8 ms 55888 KB Output is correct
78 Correct 8 ms 55888 KB Output is correct
79 Correct 9 ms 56056 KB Output is correct
80 Correct 8 ms 55888 KB Output is correct
81 Correct 16 ms 55900 KB Output is correct
82 Correct 8 ms 56060 KB Output is correct
83 Correct 8 ms 55948 KB Output is correct
84 Correct 8 ms 55888 KB Output is correct
85 Correct 8 ms 55888 KB Output is correct
86 Correct 8 ms 55860 KB Output is correct
87 Correct 8 ms 55888 KB Output is correct
88 Correct 11 ms 55888 KB Output is correct
89 Correct 37 ms 56392 KB Output is correct
90 Correct 67 ms 55888 KB Output is correct
91 Correct 56 ms 56716 KB Output is correct
92 Correct 128 ms 93256 KB Output is correct
93 Correct 232 ms 101448 KB Output is correct
94 Correct 352 ms 110204 KB Output is correct
95 Correct 171 ms 95304 KB Output is correct
96 Correct 168 ms 95304 KB Output is correct
97 Correct 176 ms 95540 KB Output is correct
98 Correct 260 ms 102224 KB Output is correct
99 Correct 202 ms 102216 KB Output is correct
100 Correct 334 ms 102216 KB Output is correct
101 Correct 333 ms 102216 KB Output is correct
102 Correct 378 ms 102216 KB Output is correct
103 Correct 657 ms 114584 KB Output is correct
104 Correct 399 ms 127164 KB Output is correct
105 Correct 366 ms 118112 KB Output is correct
106 Correct 380 ms 108736 KB Output is correct
107 Correct 223 ms 110272 KB Output is correct
108 Correct 402 ms 106432 KB Output is correct
109 Correct 219 ms 110360 KB Output is correct
110 Correct 51 ms 56904 KB Output is correct
111 Correct 39 ms 56648 KB Output is correct
112 Correct 228 ms 105544 KB Output is correct
113 Correct 4175 ms 99400 KB Output is correct
114 Correct 190 ms 105436 KB Output is correct
115 Correct 62 ms 92612 KB Output is correct
116 Correct 276 ms 102632 KB Output is correct
117 Correct 349 ms 110396 KB Output is correct
118 Correct 75 ms 92488 KB Output is correct
119 Correct 77 ms 92704 KB Output is correct
120 Correct 25 ms 59472 KB Output is correct
121 Correct 292 ms 102224 KB Output is correct
122 Correct 298 ms 102216 KB Output is correct
123 Correct 3032 ms 101572 KB Output is correct
124 Correct 141 ms 101640 KB Output is correct
125 Correct 3400 ms 102080 KB Output is correct
126 Correct 370 ms 116040 KB Output is correct
127 Correct 1454 ms 105020 KB Output is correct
128 Correct 1305 ms 105104 KB Output is correct
129 Execution timed out 5070 ms 104036 KB Time limit exceeded
130 Halted 0 ms 0 KB -