oj.uz

Submission #1110345

# Submission time Handle Problem Language Result Execution time Memory
1110345 2024-11-09T09:46:13 Z 8pete8 Jail (JOI22_jail) C++17
100 / 100
 2512 ms 80628 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,int x){
    t.update(tin[S[i]],{tin[T[i]],i},x);
    t.update(tin[T[i]],{tin[S[i]],i},x);
    t2.update(tin[S[i]],{tin[T[i]],i},x);
    t2.update(tin[T[i]],{tin[S[i]],i},x);
    t3.update(tin[T[i]],{i,i},x);
}
bool findcycle(int cur){
    if(on[cur])return 1;
    if(vis[cur])return 0;
    vis[cur]=on[cur]=1;
    vector<int>move;
    del(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;
        }
        go=t.qry(tin[adj[S[cur]][x]],tout[adj[S[cur]][x]]);
        if(go.f!=inf&&go.f!=minf&&go.f>tout[adj[S[cur]][x]]){
            if(on[go.s])return 1;
            move.pb(go.s);
            del(go.s,1);
        }
        else x++;
    }
    x=0;
    while(x<adj[S[cur]].size()){
        if(adj[S[cur]][x]==up[S[cur]][0]){
            x++;
            continue;
        }
        go=t2.qry(tin[adj[S[cur]][x]],tout[adj[S[cur]][x]]);
        
        if(go.f!=inf&&go.f!=minf&&go.f<tin[adj[S[cur]][x]]){
            if(on[go.s])return 1;
            move.pb(go.s);
            del(go.s,1);
        }
        else x++;
    }
    int curhvy=S[cur],node=lca(S[cur],T[cur]);
    while(hvyp[curhvy]!=hvyp[node]){
        go=t3.qry(tin[hvyp[curhvy]],tin[curhvy]);
        if(go.f!=inf&&go.f!=minf){
            if(on[go.s])return 1;
            move.pb(go.s);
            del(go.s,1);
        }
        
        else curhvy=up[hvyp[curhvy]][0];
    }
    while(1){
        go=t3.qry(tin[node],tin[curhvy]);
        if(go.f!=inf&&go.f!=minf){
            if(on[go.s])return 1;
            move.pb(go.s);
            del(go.s,1);
        }
        else break;
    }
    curhvy=T[cur];
    while(hvyp[curhvy]!=hvyp[node]){
        go=t3.qry(tin[hvyp[curhvy]],tin[curhvy]);
        if(go.f!=inf&&go.f!=minf){
            if(on[go.s])return 1;
            move.pb(go.s);
            del(go.s,1);
        }
        else curhvy=up[hvyp[curhvy]][0];
    }
    while(1){
        go=t3.qry(tin[node],tin[curhvy]);
        if(go.f!=inf&&go.f!=minf){
            if(on[go.s])return 1;
            move.pb(go.s);
            del(go.s,1);
        }
        else break;
    }
    del(cur,0);
    for(auto j:move)del(j,0);
    for(auto j:move){
        if(vis[j])continue;
        if(on[j])return 1;
        if(findcycle(j))return 1;
    }
    del(cur,1);
    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++)del(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)break;
    }
    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:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  137 | void del(int i,int x){
      |                     ^
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:152:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     while(x<adj[S[cur]].size()){
      |           ~^~~~~~~~~~~~~~~~~~~
jail.cpp:166:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     while(x<adj[S[cur]].size()){
      |           ~^~~~~~~~~~~~~~~~~~~
jail.cpp: At global scope:
jail.cpp:230:12: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  230 | void solve(){
      |            ^
jail.cpp: In function 'void solve()':
jail.cpp:257:36: warning: operation on 'vis[i]' may be undefined [-Wsequence-point]
  257 |         adj[i].clear(),on[i]=vis[i]=S[i]=T[i]=vis[i]=0;
      |                              ~~~~~~^~~~~~~~~~~~~~~~~~~
jail.cpp: At global scope:
jail.cpp:263:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  263 | 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 6 ms 26448 KB Output is correct
2 Correct 5 ms 26448 KB Output is correct
3 Correct 5 ms 26448 KB Output is correct
4 Correct 14 ms 26524 KB Output is correct
5 Correct 22 ms 26448 KB Output is correct
6 Correct 5 ms 26448 KB Output is correct
7 Correct 6 ms 26448 KB Output is correct
8 Correct 9 ms 26504 KB Output is correct
9 Correct 51 ms 29772 KB Output is correct
10 Correct 52 ms 53836 KB Output is correct
11 Correct 14 ms 26448 KB Output is correct
12 Correct 57 ms 26512 KB Output is correct
13 Correct 206 ms 62024 KB Output is correct
14 Correct 141 ms 62024 KB Output is correct
15 Correct 196 ms 60620 KB Output is correct
16 Correct 434 ms 65608 KB Output is correct
17 Correct 180 ms 64548 KB Output is correct
18 Correct 301 ms 65352 KB Output is correct
19 Correct 174 ms 63304 KB Output is correct
20 Correct 117 ms 63304 KB Output is correct
21 Correct 161 ms 63556 KB Output is correct
22 Correct 162 ms 63600 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 4 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 5 ms 26448 KB Output is correct
6 Correct 5 ms 26448 KB Output is correct
7 Correct 6 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 6 ms 26448 KB Output is correct
11 Correct 6 ms 26448 KB Output is correct
12 Correct 6 ms 26448 KB Output is correct
13 Correct 5 ms 26496 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 4 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 5 ms 26448 KB Output is correct
6 Correct 5 ms 26448 KB Output is correct
7 Correct 6 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 6 ms 26448 KB Output is correct
11 Correct 6 ms 26448 KB Output is correct
12 Correct 6 ms 26448 KB Output is correct
13 Correct 5 ms 26496 KB Output is correct
14 Correct 5 ms 26616 KB Output is correct
15 Correct 5 ms 26476 KB Output is correct
16 Correct 6 ms 26448 KB Output is correct
17 Correct 6 ms 26448 KB Output is correct
18 Correct 6 ms 26448 KB Output is correct
19 Correct 5 ms 26448 KB Output is correct
20 Correct 6 ms 26620 KB Output is correct
21 Correct 5 ms 26448 KB Output is correct
22 Correct 7 ms 26448 KB Output is correct
23 Correct 6 ms 26616 KB Output is correct
24 Correct 5 ms 26448 KB Output is correct
25 Correct 6 ms 26700 KB Output is correct
26 Correct 6 ms 26452 KB Output is correct
27 Correct 6 ms 26448 KB Output is correct
28 Correct 5 ms 26448 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 4 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 5 ms 26448 KB Output is correct
6 Correct 5 ms 26448 KB Output is correct
7 Correct 6 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 6 ms 26448 KB Output is correct
11 Correct 6 ms 26448 KB Output is correct
12 Correct 6 ms 26448 KB Output is correct
13 Correct 5 ms 26496 KB Output is correct
14 Correct 5 ms 26616 KB Output is correct
15 Correct 5 ms 26476 KB Output is correct
16 Correct 6 ms 26448 KB Output is correct
17 Correct 6 ms 26448 KB Output is correct
18 Correct 6 ms 26448 KB Output is correct
19 Correct 5 ms 26448 KB Output is correct
20 Correct 6 ms 26620 KB Output is correct
21 Correct 5 ms 26448 KB Output is correct
22 Correct 7 ms 26448 KB Output is correct
23 Correct 6 ms 26616 KB Output is correct
24 Correct 5 ms 26448 KB Output is correct
25 Correct 6 ms 26700 KB Output is correct
26 Correct 6 ms 26452 KB Output is correct
27 Correct 6 ms 26448 KB Output is correct
28 Correct 5 ms 26448 KB Output is correct
29 Correct 8 ms 26448 KB Output is correct
30 Correct 7 ms 26448 KB Output is correct
31 Correct 6 ms 26448 KB Output is correct
32 Correct 7 ms 26448 KB Output is correct
33 Correct 7 ms 26448 KB Output is correct
34 Correct 9 ms 26448 KB Output is correct
35 Correct 10 ms 26448 KB Output is correct
36 Correct 9 ms 26448 KB Output is correct
37 Correct 7 ms 26528 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 4 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 5 ms 26448 KB Output is correct
6 Correct 5 ms 26448 KB Output is correct
7 Correct 6 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 6 ms 26448 KB Output is correct
11 Correct 6 ms 26448 KB Output is correct
12 Correct 6 ms 26448 KB Output is correct
13 Correct 5 ms 26496 KB Output is correct
14 Correct 5 ms 26616 KB Output is correct
15 Correct 5 ms 26476 KB Output is correct
16 Correct 6 ms 26448 KB Output is correct
17 Correct 6 ms 26448 KB Output is correct
18 Correct 6 ms 26448 KB Output is correct
19 Correct 5 ms 26448 KB Output is correct
20 Correct 6 ms 26620 KB Output is correct
21 Correct 5 ms 26448 KB Output is correct
22 Correct 7 ms 26448 KB Output is correct
23 Correct 6 ms 26616 KB Output is correct
24 Correct 5 ms 26448 KB Output is correct
25 Correct 6 ms 26700 KB Output is correct
26 Correct 6 ms 26452 KB Output is correct
27 Correct 6 ms 26448 KB Output is correct
28 Correct 5 ms 26448 KB Output is correct
29 Correct 8 ms 26448 KB Output is correct
30 Correct 7 ms 26448 KB Output is correct
31 Correct 6 ms 26448 KB Output is correct
32 Correct 7 ms 26448 KB Output is correct
33 Correct 7 ms 26448 KB Output is correct
34 Correct 9 ms 26448 KB Output is correct
35 Correct 10 ms 26448 KB Output is correct
36 Correct 9 ms 26448 KB Output is correct
37 Correct 7 ms 26528 KB Output is correct
38 Correct 52 ms 29768 KB Output is correct
39 Correct 55 ms 53844 KB Output is correct
40 Correct 52 ms 29512 KB Output is correct
41 Correct 52 ms 30024 KB Output is correct
42 Correct 50 ms 29756 KB Output is correct
43 Correct 32 ms 29264 KB Output is correct
44 Correct 27 ms 26704 KB Output is correct
45 Correct 54 ms 42820 KB Output is correct
46 Correct 54 ms 42828 KB Output is correct
47 Correct 81 ms 48200 KB Output is correct
48 Correct 84 ms 49320 KB Output is correct
49 Correct 56 ms 43096 KB Output is correct
50 Correct 57 ms 42832 KB Output is correct
51 Correct 47 ms 44468 KB Output is correct
52 Correct 48 ms 44624 KB Output is correct
53 Correct 31 ms 29000 KB Output is correct
54 Correct 60 ms 42724 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 6 ms 26448 KB Output is correct
3 Correct 5 ms 26448 KB Output is correct
4 Correct 5 ms 26676 KB Output is correct
5 Correct 14 ms 26460 KB Output is correct
6 Correct 5 ms 26448 KB Output is correct
7 Correct 6 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 26448 KB Output is correct
11 Correct 5 ms 26448 KB Output is correct
12 Correct 8 ms 26448 KB Output is correct
13 Correct 34 ms 26960 KB Output is correct
14 Correct 55 ms 26448 KB Output is correct
15 Correct 57 ms 26448 KB Output is correct
16 Correct 67 ms 45644 KB Output is correct
17 Correct 145 ms 50640 KB Output is correct
18 Correct 235 ms 54088 KB Output is correct
19 Correct 135 ms 45644 KB Output is correct
20 Correct 83 ms 45600 KB Output is correct
21 Correct 146 ms 45856 KB Output is correct
22 Correct 209 ms 52448 KB Output is correct
23 Correct 182 ms 52444 KB Output is correct
24 Correct 334 ms 52680 KB Output is correct
25 Correct 209 ms 52552 KB Output is correct
26 Correct 308 ms 52684 KB Output is correct
27 Correct 710 ms 60932 KB Output is correct
28 Correct 598 ms 80628 KB Output is correct
29 Correct 420 ms 66836 KB Output is correct
30 Correct 407 ms 62916 KB Output is correct
31 Correct 318 ms 65476 KB Output is correct
32 Correct 391 ms 58868 KB Output is correct
33 Correct 292 ms 65476 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26448 KB Output is correct
2 Correct 5 ms 26448 KB Output is correct
3 Correct 5 ms 26448 KB Output is correct
4 Correct 14 ms 26524 KB Output is correct
5 Correct 22 ms 26448 KB Output is correct
6 Correct 5 ms 26448 KB Output is correct
7 Correct 6 ms 26448 KB Output is correct
8 Correct 9 ms 26504 KB Output is correct
9 Correct 51 ms 29772 KB Output is correct
10 Correct 52 ms 53836 KB Output is correct
11 Correct 14 ms 26448 KB Output is correct
12 Correct 57 ms 26512 KB Output is correct
13 Correct 206 ms 62024 KB Output is correct
14 Correct 141 ms 62024 KB Output is correct
15 Correct 196 ms 60620 KB Output is correct
16 Correct 434 ms 65608 KB Output is correct
17 Correct 180 ms 64548 KB Output is correct
18 Correct 301 ms 65352 KB Output is correct
19 Correct 174 ms 63304 KB Output is correct
20 Correct 117 ms 63304 KB Output is correct
21 Correct 161 ms 63556 KB Output is correct
22 Correct 162 ms 63600 KB Output is correct
23 Correct 5 ms 26448 KB Output is correct
24 Correct 4 ms 26448 KB Output is correct
25 Correct 5 ms 26620 KB Output is correct
26 Correct 7 ms 26448 KB Output is correct
27 Correct 5 ms 26448 KB Output is correct
28 Correct 5 ms 26448 KB Output is correct
29 Correct 6 ms 26448 KB Output is correct
30 Correct 5 ms 26448 KB Output is correct
31 Correct 5 ms 26448 KB Output is correct
32 Correct 6 ms 26448 KB Output is correct
33 Correct 6 ms 26448 KB Output is correct
34 Correct 6 ms 26448 KB Output is correct
35 Correct 5 ms 26496 KB Output is correct
36 Correct 5 ms 26616 KB Output is correct
37 Correct 5 ms 26476 KB Output is correct
38 Correct 6 ms 26448 KB Output is correct
39 Correct 6 ms 26448 KB Output is correct
40 Correct 6 ms 26448 KB Output is correct
41 Correct 5 ms 26448 KB Output is correct
42 Correct 6 ms 26620 KB Output is correct
43 Correct 5 ms 26448 KB Output is correct
44 Correct 7 ms 26448 KB Output is correct
45 Correct 6 ms 26616 KB Output is correct
46 Correct 5 ms 26448 KB Output is correct
47 Correct 6 ms 26700 KB Output is correct
48 Correct 6 ms 26452 KB Output is correct
49 Correct 6 ms 26448 KB Output is correct
50 Correct 5 ms 26448 KB Output is correct
51 Correct 8 ms 26448 KB Output is correct
52 Correct 7 ms 26448 KB Output is correct
53 Correct 6 ms 26448 KB Output is correct
54 Correct 7 ms 26448 KB Output is correct
55 Correct 7 ms 26448 KB Output is correct
56 Correct 9 ms 26448 KB Output is correct
57 Correct 10 ms 26448 KB Output is correct
58 Correct 9 ms 26448 KB Output is correct
59 Correct 7 ms 26528 KB Output is correct
60 Correct 52 ms 29768 KB Output is correct
61 Correct 55 ms 53844 KB Output is correct
62 Correct 52 ms 29512 KB Output is correct
63 Correct 52 ms 30024 KB Output is correct
64 Correct 50 ms 29756 KB Output is correct
65 Correct 32 ms 29264 KB Output is correct
66 Correct 27 ms 26704 KB Output is correct
67 Correct 54 ms 42820 KB Output is correct
68 Correct 54 ms 42828 KB Output is correct
69 Correct 81 ms 48200 KB Output is correct
70 Correct 84 ms 49320 KB Output is correct
71 Correct 56 ms 43096 KB Output is correct
72 Correct 57 ms 42832 KB Output is correct
73 Correct 47 ms 44468 KB Output is correct
74 Correct 48 ms 44624 KB Output is correct
75 Correct 31 ms 29000 KB Output is correct
76 Correct 60 ms 42724 KB Output is correct
77 Correct 5 ms 26448 KB Output is correct
78 Correct 6 ms 26448 KB Output is correct
79 Correct 5 ms 26448 KB Output is correct
80 Correct 5 ms 26676 KB Output is correct
81 Correct 14 ms 26460 KB Output is correct
82 Correct 5 ms 26448 KB Output is correct
83 Correct 6 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 26448 KB Output is correct
87 Correct 5 ms 26448 KB Output is correct
88 Correct 8 ms 26448 KB Output is correct
89 Correct 34 ms 26960 KB Output is correct
90 Correct 55 ms 26448 KB Output is correct
91 Correct 57 ms 26448 KB Output is correct
92 Correct 67 ms 45644 KB Output is correct
93 Correct 145 ms 50640 KB Output is correct
94 Correct 235 ms 54088 KB Output is correct
95 Correct 135 ms 45644 KB Output is correct
96 Correct 83 ms 45600 KB Output is correct
97 Correct 146 ms 45856 KB Output is correct
98 Correct 209 ms 52448 KB Output is correct
99 Correct 182 ms 52444 KB Output is correct
100 Correct 334 ms 52680 KB Output is correct
101 Correct 209 ms 52552 KB Output is correct
102 Correct 308 ms 52684 KB Output is correct
103 Correct 710 ms 60932 KB Output is correct
104 Correct 598 ms 80628 KB Output is correct
105 Correct 420 ms 66836 KB Output is correct
106 Correct 407 ms 62916 KB Output is correct
107 Correct 318 ms 65476 KB Output is correct
108 Correct 391 ms 58868 KB Output is correct
109 Correct 292 ms 65476 KB Output is correct
110 Correct 42 ms 26612 KB Output is correct
111 Correct 26 ms 26616 KB Output is correct
112 Correct 249 ms 55944 KB Output is correct
113 Correct 1536 ms 50688 KB Output is correct
114 Correct 199 ms 56160 KB Output is correct
115 Correct 52 ms 43884 KB Output is correct
116 Correct 271 ms 52472 KB Output is correct
117 Correct 243 ms 53832 KB Output is correct
118 Correct 66 ms 42820 KB Output is correct
119 Correct 60 ms 42828 KB Output is correct
120 Correct 26 ms 29536 KB Output is correct
121 Correct 321 ms 53588 KB Output is correct
122 Correct 335 ms 53480 KB Output is correct
123 Correct 1234 ms 53668 KB Output is correct
124 Correct 82 ms 52808 KB Output is correct
125 Correct 1051 ms 52876 KB Output is correct
126 Correct 398 ms 61768 KB Output is correct
127 Correct 234 ms 56064 KB Output is correct
128 Correct 151 ms 56004 KB Output is correct
129 Correct 2512 ms 56532 KB Output is correct
130 Correct 266 ms 58572 KB Output is correct