oj.uz

답안 #1005647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1005647 2024-06-22T17:13:17 Z modwwe Tourism (JOI23_tourism) C++17
100 / 100
 3245 ms 51500 KB 
/**https://www.instagram.com/_modwwe/
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    int a,b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,c;
};
struct ie
{
    int a,b,c, d,e,f;

};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
        fin(task),fou(task);
#endif
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    /// cin>>s1;
    // modwwe
    phongbeo();
    checktime
}
int t[400007];
int depth[100007];
ic a[100007];
int c[100007];
ib euler[100007];
int d[100007];
int st[17][100007];
int ans[100007];
int S;
int b[100007];
int sl[100007];
vector<int> v[100007];
int e[100007];
int pre[100007];
int nxt[100007];
bool cmp(ic a,ic b)
{
    if(a.a / S != b.a / S) return (a.a < b.a);
    else if(!((a.a / S) & 1)) return (a.b < b.b);
    else return (a.b > b.b);
}
void upd(int node,int l,int r,int l1,int r1,int cc)
{
    if(l>=l1&&r<=r1)
    {
        if(cc==1) t[node]=l;
         else t[node]=0;
        return;
    }
    int mid=l+r>>1;
    if(mid>=r1)
        upd(node<<1,l,mid,l1,r1,cc);
    else
        upd(node<<1|1,mid+1,r,l1,r1,cc);
    t[node]=max(t[node<<1],t[node<<1|1]);
}
int get1(int node,int l,int r,int l1,int r1)
{
    if(l>r1||r<l1) return 0;
    if(l>=l1&&r<=r1) return t[node];

    int mid=l+r>>1;
 int ss3=0;
    if(t[node<<1|1]!=0) ss3=get1(node<<1|1,mid+1,r,l1,r1);
    if(ss3!=0) return ss3;
else return get1(node<<1,l,mid,l1,r1);
}
void dfs(int x,int y)
{
    st[0][x]=y;
    depth[x]=depth[y]+1;
    euler[x].a=++dem;
    mx=max(mx,depth[x]);
    c[dem]=x;
    for(auto f:v[x])
        if(f!=y)
            dfs(f,x);
    euler[x].b=dem;
}
int lca(int x,int y,int cc)
{
    if(x==0||x==n+1||y==0||y==n+1) return 1;
    if(depth[x]<depth[y]) swap(x,y),cc=0;
    int ss=depth[x]-depth[y]-1;
    if(ss>=0)
        for(int j=0; j<mx; ++j)
            if(bit(ss,j))
                x=st[j][x];
    if(st[0][x]==y) return x;
    if(ss!=-1)  x=st[0][x];
    for(int j=mx-1; j>=0; --j)
        if(st[j][x]!=st[j][y])
            x=st[j][x],y=st[j][y];
    if(cc==0) return y;
    else
        return x;
}
int lca2(int x,int y)
{
    if(x==0 )return y;
    if(y==0 )return x;
    if(depth[x]<depth[y]) swap(x,y);
    int ss=depth[x]-depth[y];
    if(ss!=0)
    for(int j=0; j<mx; ++j)
        if(bit(ss,j))
            x=st[j][x];
    if(x==y) return x;
    for(int j=mx-1; j>=0; --j)
        if(st[j][x]!=st[j][y])
            x=st[j][x],y=st[j][y];
    return st[0][x];
}
/*void build2(int node,int l,int r)
{
    if(l==r)
    {
        lz[node]=b[l];
        return;
    }
    int mid=l+r>>1;
    build2(node<<1,l,mid);
    build2(node<<1|1,mid+1,r);
    lz[node]=lca2(lz[node<<1],lz[node<<1|1]);
}
int get_lca(int node,int l,int r,int l1,int r1)
{
    if(l>r1||r<l1) return 0;
    if(l>=l1&&r<=r1) return lz[node];
    int mid=l+r>>1;
    return lca2(get_lca(node<<1,l,mid,l1,r1),get_lca(node<<1|1,mid+1,r,l1,r1));
}
void add(int x)
{
    s2=get1(1,1,n,1,euler[x].a);
    /// s3=get2(1,1,n,euler[x].a,n);
    sl[x]++;
    if(sl[x]==1)
    upd(1,1,n,euler[x].a,euler[x].a,1);
    if(d[x]!=0||sl[x]>1) return;
    s2=c[s2];
    s3=nxt[s2];
    pre[x]=s2;
    nxt[x]=s3;
    nxt[s2]=x;
    pre[s3]=x;
//if(l==3&&x==1) cout<<s2<<" "<<s3<<" "<<x,down
    s2=lca(x,s2,1);
    s3=lca(x,s3,1);
    if(depth[s2]<depth[s3]) swap(s2,s3);
    if(depth[x]>=depth[s2])
    {
        s4+=depth[x]-depth[s2]+1;
        d[x]=s2;
        e[s2]=x;
    }
}
void del(int x)
{sl[x]--;
 if(sl[x]==0)
    upd(1,1,n,euler[x].a,euler[x].a,-1);
    s5=d[x];
    //s2=get1(1,1,n,euler[s5].a,euler[x].a);
    //s3=get2(1,1,n,euler[x].a,euler[s5].b);
    if(sl[x]>=1) return;
    s2=pre[x];
    s3=nxt[x];
    nxt[s2]=s3;
    if(s3!=0) pre[s3]=s2;
    pre[x]=0;
    nxt[x]=0;
    s9=s2;
    if(d[x]==0)return;
    d[x]=0;
    e[s5]=0;
    s4-=(depth[x]-depth[s5]+1);
    s2=lca(s2,x,1);
    s3=lca(s3,x,1);
    if(max(depth[s2],depth[s3])<=depth[s5]) return;
    if(st[0][s2]==s9&&depth[s2]>=depth[s3]&&d[s2]==0)
    {
        s2=s9;
        s4+=depth[s2]-depth[s5]+1;
        d[s2]=s5;
        e[s5]=s2;
        return;
    }
    if(depth[s2]<depth[s3])swap(s2,s3);
    if(depth[s5]<depth[s2])
    {
        s3=e[s2];
        e[s2]=0;
        e[s5]=s3;
        d[s3]=s5;
        s4+=(depth[s2]-depth[s5]);
    }
}
void go(int x,int y)
{
    while(r<y)
    {
        ++r;
        add(b[r]);

    }
    while(l>x)
    {
        --l;

        add(b[l]);
        //cout<<l<<" "<<s4,down

    }
    //cout<<s4<<" "<<x<<" "<<y,down
    while(l<x)
    {
        del(b[l]);
        ++l;
    }
    while(r>y)
    {
        del(b[r]);

        --r;
    }

}
#define getchar_unlocked getchar

inline int scan(){
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9'){
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}
void phongbeo()
{
  //cin>>n>>m>>k;
  n=scan();
m=scan();
k=scan();
    S=sqrt(m);
    for(int i=1; i<n; ++i)
      l=scan(),r=scan(),v[l].pb(r),v[r].pb(l);

    dfs(1,0);
 mx=log2(mx)+1;
if(mx>17) mx=17;
    for(int i=1; i<mx; ++i)
        for(int j=1; j<=n; ++j)
            st[i][j]=st[i-1][st[i-1][j]];
    for(int i=1; i<=m; ++i)
        b[i]=scan();
    for(int i=1; i<=k; ++i)
       a[i].a=scan(),a[i].b=scan(),a[i].c=i;
    sort(a+1,a+1+k,cmp);
    l=1;
    r=0;
    for(int i=1; i<=k; ++i)
    {
        go(a[i].a,a[i].b);
        s3=t[1];
        s5=nxt[0];
        s3=c[s3];
        s3=lca2(s3,s5);
        ans[a[i].c]=s4+depth[1]-depth[s3];
    }
   for(int i=1; i<=k; ++i)
        printf("%d",ans[i]),
               printf("\n");
}

/*
8 8 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 6 4 3 5 2 4 7
2 8
1 2

*/
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>

using namespace std;

// #define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define isz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

const int N=1e5+1, S=400, LG=18;

struct Query{
   int l, r, i;

   Query(int a=0, int b=0, int c=0): l(a), r(b), i(c){}

   bool operator<(const Query& x){
      return l/S!=x.l/S?l<x.l:((l/S)&1?r<x.r:r>x.r);
   }
} qq[N];

struct FenwickTree{
   int n;
   vector<int> t;
   void init(int _n){
      n=_n;
      t.assign(n+1, 0);
   }
   void update(int pos, int val){
      for (int i=pos; i<=n; i+=i&(-i)) t[i]+=val;
   }
   int get(int pos){
      int ans=0;
      for (int i=pos; i; i-=i&(-i)) ans+=t[i];
      return ans;
   }
   int lower_bound(int val){
      int ans=0;
      for (int i=16; i>=0; --i) if (ans+(1<<i)<=n && t[ans+(1<<i)]<val){
         ans+=1<<i;
         val-=t[ans];
      }
      return ans+1;
   }
};

int n, m, q, a[N], tdfs, tin[N], tout[N], dep[N], ans[N], cnt[N], tour[N];
int tin2[N], tout2[N], tdfs2;
pair<int, int> st[N*2][LG];
vector<int> g[N];

void dfs(int u, int p){
   tin[u]=++tdfs;
   tin2[u]=++tdfs2;
   tour[tdfs2]=u;
   dep[u]=dep[p]+1;
   st[tdfs][0]={dep[u], u};
   for (int v:g[u]) if (v!=p){
      dfs(v, u);
      ++tdfs;
      st[tdfs][0]={dep[u], u};
   }
   tout[u]=tdfs;
   tout2[u]=tdfs2;
}

void build(){
   for (int k=1; k<LG; ++k) for (int i=1; i+(1<<k)-1<=tdfs; ++i) st[i][k]=min(st[i][k-1], st[i+(1<<(k-1))][k-1]);
}

int lca(int u, int v){
   u=tin[u]; v=tin[v];
   if (u>v) swap(u, v);
   int lg=__lg(v-u+1);
   return min(st[u][lg], st[v-(1<<lg)+1][lg]).second;
}

int distance(int u, int v){
   return dep[u]+dep[v]-dep[lca(u, v)]*2;
}

namespace among{
   struct SUS{
      int prev_arr[N], next_arr[N];
      int size;
      FenwickTree bit;
      int ans;
      int get_order(int x){
         return bit.get(x);
      }
      int find_by_order(int i){
         return bit.lower_bound(i);
      }
      int find_first(){
         return bit.lower_bound(1);
      }
      int find_last(){
         return bit.lower_bound(size);
      }
      void insert(int x){
         if (size){
            int i=get_order(x);
            int prev=i?find_by_order(i):find_last();
            int next=next_arr[prev];
            ans-=distance(tour[prev], tour[next]);
            ans+=distance(tour[prev], tour[x]);
            ans+=distance(tour[x], tour[next]);
            prev_arr[x]=prev; next_arr[prev]=x;
            prev_arr[next]=x; next_arr[x]=next;
         }
         bit.update(x, 1);
         if (!size){
            prev_arr[x]=x;
            next_arr[x]=x;
         }
         ++size;
      }
      void erase(int x){
         bit.update(x, -1);
         --size;
         if (size){
            int prev=prev_arr[x];
            int next=next_arr[x];
            ans+=distance(tour[prev], tour[next]);
            ans-=distance(tour[prev], tour[x]);
            ans-=distance(tour[x], tour[next]);
            prev_arr[next]=prev; next_arr[prev]=next;
         }
      }
   } us;
}

void solve(){
   #ifdef sus
   freopen("03-04.txt", "r", stdin);
   freopen("cf.out", "w", stdout);
   #endif
   cin >> n >> m >> q;
   for (int i=1; i<n; ++i){
      int x, y; cin >> x >> y;
      g[x].push_back(y);
      g[y].push_back(x);
   }
   dfs(1, 0);
   build();
   for (int i=1; i<=m; ++i) cin >> a[i];
   for (int i=1; i<=q; ++i){
      int x, y; cin >> x >> y;
      qq[i]={x, y, i};
   }
   sort(qq+1, qq+q+1);
   int cl=1, cr=0;
   among::us.bit.init(n*2);
   for (int i=1; i<=q; ++i){
      int l=qq[i].l, r=qq[i].r;
      while (l<cl){
         --cl;
         if (!cnt[tin2[a[cl]]]) among::us.insert(tin2[a[cl]]);
         ++cnt[tin2[a[cl]]];
      }
      while (r>cr){
         ++cr;
         if (!cnt[tin2[a[cr]]]) among::us.insert(tin2[a[cr]]);
         ++cnt[tin2[a[cr]]];
      }
      while (l>cl){
         --cnt[tin2[a[cl]]];
         if (!cnt[tin2[a[cl]]]) among::us.erase(tin2[a[cl]]);
         ++cl;
      }
      while (r<cr){
         --cnt[tin2[a[cr]]];
         if (!cnt[tin2[a[cr]]]) among::us.erase(tin2[a[cr]]);
         --cr;
      }
      ans[qq[i].i]=among::us.ans/2+1;
   }
   for (int i=1; i<=q; ++i) cout << ans[i] << '\n';
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve();
   return 0;
}

Compilation message

tourism.cpp:150:1: warning: "/*" within comment [-Wcomment]
  150 | /*void build2(int node,int l,int r)
      |  
tourism.cpp:315:1: warning: "/*" within comment [-Wcomment]
  315 | /*
      |

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7512 KB Output is correct
2 Correct 1 ms 7512 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 2 ms 7540 KB Output is correct
8 Correct 2 ms 7540 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7616 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 1 ms 7516 KB Output is correct
14 Correct 1 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 3 ms 7636 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7512 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7516 KB Output is correct
21 Correct 2 ms 7516 KB Output is correct
22 Correct 2 ms 7516 KB Output is correct
23 Correct 2 ms 7516 KB Output is correct
24 Correct 2 ms 7516 KB Output is correct
25 Correct 2 ms 7512 KB Output is correct
26 Correct 2 ms 7516 KB Output is correct
27 Correct 2 ms 7596 KB Output is correct
28 Correct 2 ms 7516 KB Output is correct
29 Correct 2 ms 7516 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7512 KB Output is correct
2 Correct 1 ms 7512 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 2 ms 7540 KB Output is correct
8 Correct 2 ms 7540 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7616 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 1 ms 7516 KB Output is correct
14 Correct 1 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 3 ms 7636 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7512 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7516 KB Output is correct
21 Correct 2 ms 7516 KB Output is correct
22 Correct 2 ms 7516 KB Output is correct
23 Correct 2 ms 7516 KB Output is correct
24 Correct 2 ms 7516 KB Output is correct
25 Correct 2 ms 7512 KB Output is correct
26 Correct 2 ms 7516 KB Output is correct
27 Correct 2 ms 7596 KB Output is correct
28 Correct 2 ms 7516 KB Output is correct
29 Correct 2 ms 7516 KB Output is correct
30 Correct 8 ms 7516 KB Output is correct
31 Correct 11 ms 7512 KB Output is correct
32 Correct 13 ms 7516 KB Output is correct
33 Correct 11 ms 7732 KB Output is correct
34 Correct 10 ms 7516 KB Output is correct
35 Correct 3 ms 7516 KB Output is correct
36 Correct 3 ms 7516 KB Output is correct
37 Correct 3 ms 7516 KB Output is correct
38 Correct 10 ms 7772 KB Output is correct
39 Correct 9 ms 7772 KB Output is correct
40 Correct 11 ms 7768 KB Output is correct
41 Correct 3 ms 7772 KB Output is correct
42 Correct 2 ms 7772 KB Output is correct
43 Correct 3 ms 7772 KB Output is correct
44 Correct 11 ms 7780 KB Output is correct
45 Correct 10 ms 7768 KB Output is correct
46 Correct 10 ms 7768 KB Output is correct
47 Correct 4 ms 7772 KB Output is correct
48 Correct 4 ms 7768 KB Output is correct
49 Correct 3 ms 7772 KB Output is correct
50 Correct 10 ms 7736 KB Output is correct
51 Correct 10 ms 7740 KB Output is correct
52 Correct 10 ms 7516 KB Output is correct
53 Correct 9 ms 7516 KB Output is correct
54 Correct 10 ms 7736 KB Output is correct
55 Correct 11 ms 7740 KB Output is correct
56 Correct 2 ms 7516 KB Output is correct
57 Correct 2 ms 7516 KB Output is correct
58 Correct 3 ms 7516 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7768 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 1372 ms 31908 KB Output is correct
5 Correct 1018 ms 41556 KB Output is correct
6 Correct 1519 ms 46944 KB Output is correct
7 Correct 2352 ms 48708 KB Output is correct
8 Correct 2377 ms 48724 KB Output is correct
9 Correct 2317 ms 48720 KB Output is correct
10 Correct 2393 ms 48700 KB Output is correct
11 Correct 2223 ms 48712 KB Output is correct
12 Correct 217 ms 48724 KB Output is correct
13 Correct 238 ms 48720 KB Output is correct
14 Correct 263 ms 48724 KB Output is correct
15 Correct 48 ms 47700 KB Output is correct
16 Correct 124 ms 48248 KB Output is correct
17 Correct 49 ms 7760 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 50 ms 25212 KB Output is correct
3 Correct 76 ms 27384 KB Output is correct
4 Correct 64 ms 30004 KB Output is correct
5 Correct 59 ms 40272 KB Output is correct
6 Correct 69 ms 40276 KB Output is correct
7 Correct 77 ms 40276 KB Output is correct
8 Correct 82 ms 40280 KB Output is correct
9 Correct 85 ms 40300 KB Output is correct
10 Correct 100 ms 40332 KB Output is correct
11 Correct 111 ms 40272 KB Output is correct
12 Correct 94 ms 40272 KB Output is correct
13 Correct 112 ms 40276 KB Output is correct
14 Correct 119 ms 40468 KB Output is correct
15 Correct 123 ms 40528 KB Output is correct
16 Correct 93 ms 40276 KB Output is correct
17 Correct 100 ms 40276 KB Output is correct
18 Correct 89 ms 40272 KB Output is correct
19 Correct 60 ms 40272 KB Output is correct
20 Correct 56 ms 40272 KB Output is correct
21 Correct 68 ms 40352 KB Output is correct
22 Correct 75 ms 40276 KB Output is correct
23 Correct 77 ms 40248 KB Output is correct
24 Correct 92 ms 40356 KB Output is correct
25 Correct 74 ms 40272 KB Output is correct
26 Correct 77 ms 40272 KB Output is correct
27 Correct 90 ms 40272 KB Output is correct
28 Correct 106 ms 40272 KB Output is correct
29 Correct 106 ms 40392 KB Output is correct
30 Correct 124 ms 40276 KB Output is correct
31 Correct 104 ms 40272 KB Output is correct
32 Correct 104 ms 40592 KB Output is correct
33 Correct 107 ms 40400 KB Output is correct
34 Correct 134 ms 40784 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 1704 ms 27928 KB Output is correct
5 Correct 1807 ms 27988 KB Output is correct
6 Correct 2446 ms 37652 KB Output is correct
7 Correct 2640 ms 40884 KB Output is correct
8 Correct 2678 ms 40888 KB Output is correct
9 Correct 2706 ms 40880 KB Output is correct
10 Correct 2859 ms 40892 KB Output is correct
11 Correct 3245 ms 40896 KB Output is correct
12 Correct 3080 ms 40880 KB Output is correct
13 Correct 2956 ms 40888 KB Output is correct
14 Correct 59 ms 7692 KB Output is correct

Subtask #6
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7512 KB Output is correct
2 Correct 1 ms 7512 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 2 ms 7540 KB Output is correct
8 Correct 2 ms 7540 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7616 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 1 ms 7516 KB Output is correct
14 Correct 1 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 3 ms 7636 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7512 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7516 KB Output is correct
21 Correct 2 ms 7516 KB Output is correct
22 Correct 2 ms 7516 KB Output is correct
23 Correct 2 ms 7516 KB Output is correct
24 Correct 2 ms 7516 KB Output is correct
25 Correct 2 ms 7512 KB Output is correct
26 Correct 2 ms 7516 KB Output is correct
27 Correct 2 ms 7596 KB Output is correct
28 Correct 2 ms 7516 KB Output is correct
29 Correct 2 ms 7516 KB Output is correct
30 Correct 8 ms 7516 KB Output is correct
31 Correct 11 ms 7512 KB Output is correct
32 Correct 13 ms 7516 KB Output is correct
33 Correct 11 ms 7732 KB Output is correct
34 Correct 10 ms 7516 KB Output is correct
35 Correct 3 ms 7516 KB Output is correct
36 Correct 3 ms 7516 KB Output is correct
37 Correct 3 ms 7516 KB Output is correct
38 Correct 10 ms 7772 KB Output is correct
39 Correct 9 ms 7772 KB Output is correct
40 Correct 11 ms 7768 KB Output is correct
41 Correct 3 ms 7772 KB Output is correct
42 Correct 2 ms 7772 KB Output is correct
43 Correct 3 ms 7772 KB Output is correct
44 Correct 11 ms 7780 KB Output is correct
45 Correct 10 ms 7768 KB Output is correct
46 Correct 10 ms 7768 KB Output is correct
47 Correct 4 ms 7772 KB Output is correct
48 Correct 4 ms 7768 KB Output is correct
49 Correct 3 ms 7772 KB Output is correct
50 Correct 10 ms 7736 KB Output is correct
51 Correct 10 ms 7740 KB Output is correct
52 Correct 10 ms 7516 KB Output is correct
53 Correct 9 ms 7516 KB Output is correct
54 Correct 10 ms 7736 KB Output is correct
55 Correct 11 ms 7740 KB Output is correct
56 Correct 2 ms 7516 KB Output is correct
57 Correct 2 ms 7516 KB Output is correct
58 Correct 3 ms 7516 KB Output is correct
59 Correct 2 ms 7768 KB Output is correct
60 Correct 2 ms 7512 KB Output is correct
61 Correct 2 ms 7516 KB Output is correct
62 Correct 1372 ms 31908 KB Output is correct
63 Correct 1018 ms 41556 KB Output is correct
64 Correct 1519 ms 46944 KB Output is correct
65 Correct 2352 ms 48708 KB Output is correct
66 Correct 2377 ms 48724 KB Output is correct
67 Correct 2317 ms 48720 KB Output is correct
68 Correct 2393 ms 48700 KB Output is correct
69 Correct 2223 ms 48712 KB Output is correct
70 Correct 217 ms 48724 KB Output is correct
71 Correct 238 ms 48720 KB Output is correct
72 Correct 263 ms 48724 KB Output is correct
73 Correct 48 ms 47700 KB Output is correct
74 Correct 124 ms 48248 KB Output is correct
75 Correct 49 ms 7760 KB Output is correct
76 Correct 2 ms 7512 KB Output is correct
77 Correct 50 ms 25212 KB Output is correct
78 Correct 76 ms 27384 KB Output is correct
79 Correct 64 ms 30004 KB Output is correct
80 Correct 59 ms 40272 KB Output is correct
81 Correct 69 ms 40276 KB Output is correct
82 Correct 77 ms 40276 KB Output is correct
83 Correct 82 ms 40280 KB Output is correct
84 Correct 85 ms 40300 KB Output is correct
85 Correct 100 ms 40332 KB Output is correct
86 Correct 111 ms 40272 KB Output is correct
87 Correct 94 ms 40272 KB Output is correct
88 Correct 112 ms 40276 KB Output is correct
89 Correct 119 ms 40468 KB Output is correct
90 Correct 123 ms 40528 KB Output is correct
91 Correct 93 ms 40276 KB Output is correct
92 Correct 100 ms 40276 KB Output is correct
93 Correct 89 ms 40272 KB Output is correct
94 Correct 60 ms 40272 KB Output is correct
95 Correct 56 ms 40272 KB Output is correct
96 Correct 68 ms 40352 KB Output is correct
97 Correct 75 ms 40276 KB Output is correct
98 Correct 77 ms 40248 KB Output is correct
99 Correct 92 ms 40356 KB Output is correct
100 Correct 74 ms 40272 KB Output is correct
101 Correct 77 ms 40272 KB Output is correct
102 Correct 90 ms 40272 KB Output is correct
103 Correct 106 ms 40272 KB Output is correct
104 Correct 106 ms 40392 KB Output is correct
105 Correct 124 ms 40276 KB Output is correct
106 Correct 104 ms 40272 KB Output is correct
107 Correct 104 ms 40592 KB Output is correct
108 Correct 107 ms 40400 KB Output is correct
109 Correct 134 ms 40784 KB Output is correct
110 Correct 2 ms 7512 KB Output is correct
111 Correct 2 ms 7512 KB Output is correct
112 Correct 3 ms 7516 KB Output is correct
113 Correct 1704 ms 27928 KB Output is correct
114 Correct 1807 ms 27988 KB Output is correct
115 Correct 2446 ms 37652 KB Output is correct
116 Correct 2640 ms 40884 KB Output is correct
117 Correct 2678 ms 40888 KB Output is correct
118 Correct 2706 ms 40880 KB Output is correct
119 Correct 2859 ms 40892 KB Output is correct
120 Correct 3245 ms 40896 KB Output is correct
121 Correct 3080 ms 40880 KB Output is correct
122 Correct 2956 ms 40888 KB Output is correct
123 Correct 59 ms 7692 KB Output is correct
124 Correct 2584 ms 40908 KB Output is correct
125 Correct 1448 ms 40240 KB Output is correct
126 Correct 2468 ms 40996 KB Output is correct
127 Correct 2439 ms 43856 KB Output is correct
128 Correct 2499 ms 43856 KB Output is correct
129 Correct 2536 ms 43856 KB Output is correct
130 Correct 2467 ms 43888 KB Output is correct
131 Correct 2260 ms 50416 KB Output is correct
132 Correct 2381 ms 51500 KB Output is correct
133 Correct 2310 ms 47696 KB Output is correct
134 Correct 2352 ms 43956 KB Output is correct
135 Correct 2473 ms 43936 KB Output is correct
136 Correct 2468 ms 43932 KB Output is correct
137 Correct 2284 ms 44180 KB Output is correct
138 Correct 2256 ms 44232 KB Output is correct
139 Correct 2265 ms 44172 KB Output is correct
140 Correct 2312 ms 44168 KB Output is correct
141 Correct 2438 ms 44168 KB Output is correct
142 Correct 2337 ms 44176 KB Output is correct
143 Correct 56 ms 41432 KB Output is correct
144 Correct 131 ms 43540 KB Output is correct