oj.uz

Submission #1110337

# Submission time Handle Problem Language Result Execution time Memory
1110337 2024-11-09T09:28:18 Z 8pete8 Jail (JOI22_jail) C++17
77 / 100
 5000 ms 75056 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=1e5+20000,inf=1e9,minf=-1e9,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(int)':
jail.cpp:150:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<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: 'int' and 'std::vector<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 5 ms 26448 KB Output is correct
2 Correct 5 ms 26504 KB Output is correct
3 Correct 5 ms 26448 KB Output is correct
4 Correct 14 ms 26528 KB Output is correct
5 Correct 23 ms 26616 KB Output is correct
6 Correct 6 ms 26448 KB Output is correct
7 Correct 6 ms 26448 KB Output is correct
8 Correct 8 ms 26448 KB Output is correct
9 Correct 46 ms 29768 KB Output is correct
10 Correct 53 ms 53832 KB Output is correct
11 Correct 12 ms 26448 KB Output is correct
12 Correct 54 ms 26528 KB Output is correct
13 Correct 151 ms 61768 KB Output is correct
14 Correct 119 ms 61692 KB Output is correct
15 Correct 205 ms 60488 KB Output is correct
16 Correct 444 ms 65160 KB Output is correct
17 Correct 172 ms 63280 KB Output is correct
18 Correct 280 ms 65184 KB Output is correct
19 Correct 173 ms 63312 KB Output is correct
20 Correct 161 ms 63280 KB Output is correct
21 Correct 156 ms 63352 KB Output is correct
22 Correct 133 ms 63324 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26448 KB Output is correct
2 Correct 5 ms 26448 KB Output is correct
3 Correct 6 ms 26448 KB Output is correct
4 Correct 6 ms 26448 KB Output is correct
5 Correct 5 ms 26452 KB Output is correct
6 Correct 5 ms 26460 KB Output is correct
7 Correct 6 ms 26448 KB Output is correct
8 Correct 7 ms 26456 KB Output is correct
9 Correct 5 ms 26448 KB Output is correct
10 Correct 7 ms 26448 KB Output is correct
11 Correct 5 ms 26448 KB Output is correct
12 Correct 5 ms 26460 KB Output is correct
13 Correct 5 ms 26448 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26448 KB Output is correct
2 Correct 5 ms 26448 KB Output is correct
3 Correct 6 ms 26448 KB Output is correct
4 Correct 6 ms 26448 KB Output is correct
5 Correct 5 ms 26452 KB Output is correct
6 Correct 5 ms 26460 KB Output is correct
7 Correct 6 ms 26448 KB Output is correct
8 Correct 7 ms 26456 KB Output is correct
9 Correct 5 ms 26448 KB Output is correct
10 Correct 7 ms 26448 KB Output is correct
11 Correct 5 ms 26448 KB Output is correct
12 Correct 5 ms 26460 KB Output is correct
13 Correct 5 ms 26448 KB Output is correct
14 Correct 5 ms 26448 KB Output is correct
15 Correct 4 ms 26384 KB Output is correct
16 Correct 5 ms 26448 KB Output is correct
17 Correct 6 ms 26448 KB Output is correct
18 Correct 5 ms 26448 KB Output is correct
19 Correct 5 ms 26448 KB Output is correct
20 Correct 6 ms 26448 KB Output is correct
21 Correct 5 ms 26448 KB Output is correct
22 Correct 5 ms 26544 KB Output is correct
23 Correct 5 ms 26448 KB Output is correct
24 Correct 5 ms 26448 KB Output is correct
25 Correct 5 ms 26448 KB Output is correct
26 Correct 4 ms 26448 KB Output is correct
27 Correct 5 ms 26448 KB Output is correct
28 Correct 5 ms 26700 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26448 KB Output is correct
2 Correct 5 ms 26448 KB Output is correct
3 Correct 6 ms 26448 KB Output is correct
4 Correct 6 ms 26448 KB Output is correct
5 Correct 5 ms 26452 KB Output is correct
6 Correct 5 ms 26460 KB Output is correct
7 Correct 6 ms 26448 KB Output is correct
8 Correct 7 ms 26456 KB Output is correct
9 Correct 5 ms 26448 KB Output is correct
10 Correct 7 ms 26448 KB Output is correct
11 Correct 5 ms 26448 KB Output is correct
12 Correct 5 ms 26460 KB Output is correct
13 Correct 5 ms 26448 KB Output is correct
14 Correct 5 ms 26448 KB Output is correct
15 Correct 4 ms 26384 KB Output is correct
16 Correct 5 ms 26448 KB Output is correct
17 Correct 6 ms 26448 KB Output is correct
18 Correct 5 ms 26448 KB Output is correct
19 Correct 5 ms 26448 KB Output is correct
20 Correct 6 ms 26448 KB Output is correct
21 Correct 5 ms 26448 KB Output is correct
22 Correct 5 ms 26544 KB Output is correct
23 Correct 5 ms 26448 KB Output is correct
24 Correct 5 ms 26448 KB Output is correct
25 Correct 5 ms 26448 KB Output is correct
26 Correct 4 ms 26448 KB Output is correct
27 Correct 5 ms 26448 KB Output is correct
28 Correct 5 ms 26700 KB Output is correct
29 Correct 7 ms 26616 KB Output is correct
30 Correct 7 ms 26448 KB Output is correct
31 Correct 6 ms 26448 KB Output is correct
32 Correct 8 ms 26448 KB Output is correct
33 Correct 6 ms 26500 KB Output is correct
34 Correct 8 ms 26448 KB Output is correct
35 Correct 8 ms 26448 KB Output is correct
36 Correct 7 ms 26448 KB Output is correct
37 Correct 6 ms 26448 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26448 KB Output is correct
2 Correct 5 ms 26448 KB Output is correct
3 Correct 6 ms 26448 KB Output is correct
4 Correct 6 ms 26448 KB Output is correct
5 Correct 5 ms 26452 KB Output is correct
6 Correct 5 ms 26460 KB Output is correct
7 Correct 6 ms 26448 KB Output is correct
8 Correct 7 ms 26456 KB Output is correct
9 Correct 5 ms 26448 KB Output is correct
10 Correct 7 ms 26448 KB Output is correct
11 Correct 5 ms 26448 KB Output is correct
12 Correct 5 ms 26460 KB Output is correct
13 Correct 5 ms 26448 KB Output is correct
14 Correct 5 ms 26448 KB Output is correct
15 Correct 4 ms 26384 KB Output is correct
16 Correct 5 ms 26448 KB Output is correct
17 Correct 6 ms 26448 KB Output is correct
18 Correct 5 ms 26448 KB Output is correct
19 Correct 5 ms 26448 KB Output is correct
20 Correct 6 ms 26448 KB Output is correct
21 Correct 5 ms 26448 KB Output is correct
22 Correct 5 ms 26544 KB Output is correct
23 Correct 5 ms 26448 KB Output is correct
24 Correct 5 ms 26448 KB Output is correct
25 Correct 5 ms 26448 KB Output is correct
26 Correct 4 ms 26448 KB Output is correct
27 Correct 5 ms 26448 KB Output is correct
28 Correct 5 ms 26700 KB Output is correct
29 Correct 7 ms 26616 KB Output is correct
30 Correct 7 ms 26448 KB Output is correct
31 Correct 6 ms 26448 KB Output is correct
32 Correct 8 ms 26448 KB Output is correct
33 Correct 6 ms 26500 KB Output is correct
34 Correct 8 ms 26448 KB Output is correct
35 Correct 8 ms 26448 KB Output is correct
36 Correct 7 ms 26448 KB Output is correct
37 Correct 6 ms 26448 KB Output is correct
38 Correct 42 ms 29768 KB Output is correct
39 Correct 47 ms 53932 KB Output is correct
40 Correct 63 ms 29476 KB Output is correct
41 Correct 66 ms 29168 KB Output is correct
42 Correct 47 ms 29768 KB Output is correct
43 Correct 32 ms 29008 KB Output is correct
44 Correct 33 ms 26448 KB Output is correct
45 Correct 57 ms 42824 KB Output is correct
46 Correct 64 ms 42624 KB Output is correct
47 Correct 143 ms 48380 KB Output is correct
48 Correct 165 ms 48200 KB Output is correct
49 Correct 64 ms 43040 KB Output is correct
50 Correct 65 ms 42824 KB Output is correct
51 Correct 46 ms 44616 KB Output is correct
52 Correct 44 ms 44616 KB Output is correct
53 Correct 25 ms 29008 KB Output is correct
54 Correct 72 ms 42568 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26448 KB Output is correct
2 Correct 5 ms 26448 KB Output is correct
3 Correct 5 ms 26620 KB Output is correct
4 Correct 7 ms 26448 KB Output is correct
5 Correct 12 ms 26460 KB Output is correct
6 Correct 6 ms 26616 KB Output is correct
7 Correct 5 ms 26448 KB Output is correct
8 Correct 5 ms 26448 KB Output is correct
9 Correct 5 ms 26448 KB Output is correct
10 Correct 5 ms 26512 KB Output is correct
11 Correct 5 ms 26448 KB Output is correct
12 Correct 7 ms 26448 KB Output is correct
13 Correct 34 ms 26620 KB Output is correct
14 Correct 60 ms 26508 KB Output is correct
15 Correct 59 ms 26448 KB Output is correct
16 Correct 111 ms 44360 KB Output is correct
17 Correct 191 ms 50248 KB Output is correct
18 Correct 340 ms 54092 KB Output is correct
19 Correct 164 ms 45688 KB Output is correct
20 Correct 156 ms 45620 KB Output is correct
21 Correct 178 ms 45644 KB Output is correct
22 Correct 250 ms 52312 KB Output is correct
23 Correct 189 ms 52304 KB Output is correct
24 Correct 322 ms 52296 KB Output is correct
25 Correct 333 ms 52524 KB Output is correct
26 Correct 309 ms 52296 KB Output is correct
27 Correct 601 ms 59592 KB Output is correct
28 Correct 333 ms 75056 KB Output is correct
29 Correct 319 ms 64016 KB Output is correct
30 Correct 356 ms 60700 KB Output is correct
31 Correct 195 ms 62660 KB Output is correct
32 Correct 363 ms 57284 KB Output is correct
33 Correct 199 ms 62624 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26448 KB Output is correct
2 Correct 5 ms 26504 KB Output is correct
3 Correct 5 ms 26448 KB Output is correct
4 Correct 14 ms 26528 KB Output is correct
5 Correct 23 ms 26616 KB Output is correct
6 Correct 6 ms 26448 KB Output is correct
7 Correct 6 ms 26448 KB Output is correct
8 Correct 8 ms 26448 KB Output is correct
9 Correct 46 ms 29768 KB Output is correct
10 Correct 53 ms 53832 KB Output is correct
11 Correct 12 ms 26448 KB Output is correct
12 Correct 54 ms 26528 KB Output is correct
13 Correct 151 ms 61768 KB Output is correct
14 Correct 119 ms 61692 KB Output is correct
15 Correct 205 ms 60488 KB Output is correct
16 Correct 444 ms 65160 KB Output is correct
17 Correct 172 ms 63280 KB Output is correct
18 Correct 280 ms 65184 KB Output is correct
19 Correct 173 ms 63312 KB Output is correct
20 Correct 161 ms 63280 KB Output is correct
21 Correct 156 ms 63352 KB Output is correct
22 Correct 133 ms 63324 KB Output is correct
23 Correct 5 ms 26448 KB Output is correct
24 Correct 5 ms 26448 KB Output is correct
25 Correct 6 ms 26448 KB Output is correct
26 Correct 6 ms 26448 KB Output is correct
27 Correct 5 ms 26452 KB Output is correct
28 Correct 5 ms 26460 KB Output is correct
29 Correct 6 ms 26448 KB Output is correct
30 Correct 7 ms 26456 KB Output is correct
31 Correct 5 ms 26448 KB Output is correct
32 Correct 7 ms 26448 KB Output is correct
33 Correct 5 ms 26448 KB Output is correct
34 Correct 5 ms 26460 KB Output is correct
35 Correct 5 ms 26448 KB Output is correct
36 Correct 5 ms 26448 KB Output is correct
37 Correct 4 ms 26384 KB Output is correct
38 Correct 5 ms 26448 KB Output is correct
39 Correct 6 ms 26448 KB Output is correct
40 Correct 5 ms 26448 KB Output is correct
41 Correct 5 ms 26448 KB Output is correct
42 Correct 6 ms 26448 KB Output is correct
43 Correct 5 ms 26448 KB Output is correct
44 Correct 5 ms 26544 KB Output is correct
45 Correct 5 ms 26448 KB Output is correct
46 Correct 5 ms 26448 KB Output is correct
47 Correct 5 ms 26448 KB Output is correct
48 Correct 4 ms 26448 KB Output is correct
49 Correct 5 ms 26448 KB Output is correct
50 Correct 5 ms 26700 KB Output is correct
51 Correct 7 ms 26616 KB Output is correct
52 Correct 7 ms 26448 KB Output is correct
53 Correct 6 ms 26448 KB Output is correct
54 Correct 8 ms 26448 KB Output is correct
55 Correct 6 ms 26500 KB Output is correct
56 Correct 8 ms 26448 KB Output is correct
57 Correct 8 ms 26448 KB Output is correct
58 Correct 7 ms 26448 KB Output is correct
59 Correct 6 ms 26448 KB Output is correct
60 Correct 42 ms 29768 KB Output is correct
61 Correct 47 ms 53932 KB Output is correct
62 Correct 63 ms 29476 KB Output is correct
63 Correct 66 ms 29168 KB Output is correct
64 Correct 47 ms 29768 KB Output is correct
65 Correct 32 ms 29008 KB Output is correct
66 Correct 33 ms 26448 KB Output is correct
67 Correct 57 ms 42824 KB Output is correct
68 Correct 64 ms 42624 KB Output is correct
69 Correct 143 ms 48380 KB Output is correct
70 Correct 165 ms 48200 KB Output is correct
71 Correct 64 ms 43040 KB Output is correct
72 Correct 65 ms 42824 KB Output is correct
73 Correct 46 ms 44616 KB Output is correct
74 Correct 44 ms 44616 KB Output is correct
75 Correct 25 ms 29008 KB Output is correct
76 Correct 72 ms 42568 KB Output is correct
77 Correct 5 ms 26448 KB Output is correct
78 Correct 5 ms 26448 KB Output is correct
79 Correct 5 ms 26620 KB Output is correct
80 Correct 7 ms 26448 KB Output is correct
81 Correct 12 ms 26460 KB Output is correct
82 Correct 6 ms 26616 KB Output is correct
83 Correct 5 ms 26448 KB Output is correct
84 Correct 5 ms 26448 KB Output is correct
85 Correct 5 ms 26448 KB Output is correct
86 Correct 5 ms 26512 KB Output is correct
87 Correct 5 ms 26448 KB Output is correct
88 Correct 7 ms 26448 KB Output is correct
89 Correct 34 ms 26620 KB Output is correct
90 Correct 60 ms 26508 KB Output is correct
91 Correct 59 ms 26448 KB Output is correct
92 Correct 111 ms 44360 KB Output is correct
93 Correct 191 ms 50248 KB Output is correct
94 Correct 340 ms 54092 KB Output is correct
95 Correct 164 ms 45688 KB Output is correct
96 Correct 156 ms 45620 KB Output is correct
97 Correct 178 ms 45644 KB Output is correct
98 Correct 250 ms 52312 KB Output is correct
99 Correct 189 ms 52304 KB Output is correct
100 Correct 322 ms 52296 KB Output is correct
101 Correct 333 ms 52524 KB Output is correct
102 Correct 309 ms 52296 KB Output is correct
103 Correct 601 ms 59592 KB Output is correct
104 Correct 333 ms 75056 KB Output is correct
105 Correct 319 ms 64016 KB Output is correct
106 Correct 356 ms 60700 KB Output is correct
107 Correct 195 ms 62660 KB Output is correct
108 Correct 363 ms 57284 KB Output is correct
109 Correct 199 ms 62624 KB Output is correct
110 Correct 46 ms 26448 KB Output is correct
111 Correct 34 ms 26516 KB Output is correct
112 Correct 206 ms 55880 KB Output is correct
113 Correct 3489 ms 50696 KB Output is correct
114 Correct 180 ms 56004 KB Output is correct
115 Correct 57 ms 43712 KB Output is correct
116 Correct 290 ms 52296 KB Output is correct
117 Correct 327 ms 54104 KB Output is correct
118 Correct 64 ms 42824 KB Output is correct
119 Correct 80 ms 42824 KB Output is correct
120 Correct 25 ms 29520 KB Output is correct
121 Correct 280 ms 52296 KB Output is correct
122 Correct 295 ms 52296 KB Output is correct
123 Correct 2666 ms 52732 KB Output is correct
124 Correct 112 ms 52640 KB Output is correct
125 Correct 2849 ms 52892 KB Output is correct
126 Correct 346 ms 61496 KB Output is correct
127 Correct 1250 ms 55864 KB Output is correct
128 Correct 1191 ms 55856 KB Output is correct
129 Execution timed out 5072 ms 55736 KB Time limit exceeded
130 Halted 0 ms 0 KB -