fork download
copy 
  1. /*Code by HsonW, 11/2 NH-Hue. Just a newbie <3*/
  2. /*Toi Yeu Khanh Huyen <3*/
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. using ll = long long;
  6.  
  7. struct DSU {
  8.     vector<int> p, r;
  9.     vector<ll> sz;
  10.     DSU(int n): p(n), r(n), sz(n) { iota(p.begin(), p.end(), 0); }
  11.     int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
  12.     void unite(int a, int b){
  13.         a = find(a); b = find(b);
  14.         if(a==b) return;
  15.         if(r[a]<r[b]) swap(a,b);
  16.         p[b]=a; sz[a]+=sz[b];
  17.         if(r[a]==r[b]) r[a]++;
  18.     }
  19. };
  20.  
  21. signed main(){
  22.     #define name "K Huyen"
  23.     ios::sync_with_stdio(0);
  24.     cin.tie(NULL);
  25.     if(fopen(name ".inp","r")){
  26.         freopen(name ".inp","r",stdin);
  27.         freopen(name ".out","w",stdout);
  28.     }
  29.     int T;
  30.     cin >> T;
  31.     while(T--){
  32.         int n;
  33.         cin >> n;
  34.         string s;
  35.         cin >> s;
  36.         s = " " + s;
  37.         vector<int> u(n+1,-1), l(n+1,-1), d(n+1,-1);
  38.         int id=0;
  39.         for(int i=1;i<=n;i++){
  40.             if(s[i]=='0' && i>1) u[i]=id++;
  41.             if(s[i]=='0' && i<n) l[i]=id++;
  42.             if(s[i]=='1')      d[i]=id++;
  43.         }
  44.         DSU ds(id);
  45.         for(int i=1;i<=n;i++){
  46.             if(u[i]>=0) ds.sz[u[i]] = i-1;
  47.             if(l[i]>=0) ds.sz[l[i]] = n-i;
  48.             if(d[i]>=0) ds.sz[d[i]] = 1;
  49.         }
  50.         for(int i=2;i<=n;i++){
  51.             if(u[i]>=0 && u[i-1]>=0) ds.unite(u[i],u[i-1]);
  52.         }
  53.         for(int i=1;i<n;i++){
  54.             if(l[i]>=0 && l[i+1]>=0) ds.unite(l[i],l[i+1]);
  55.         }
  56.         for(int i=2;i<=n;i++){
  57.             if(d[i]>=0 && l[i-1]>=0) ds.unite(d[i],l[i-1]);
  58.         }
  59.         for(int i=1;i<n;i++){
  60.             if(d[i]>=0 && u[i+1]>=0) ds.unite(d[i],u[i+1]);
  61.         }
  62.         for(int i=2;i<=n;i++){
  63.             if(u[i]>=0 && d[i-1]>=0) ds.unite(u[i],d[i-1]);
  64.         }
  65.         for(int i=1;i<n;i++){
  66.             if(l[i]>=0 && d[i+1]>=0) ds.unite(l[i],d[i+1]);
  67.         }
  68.         ll ans=0;
  69.         for(int i=0;i<id;i++){
  70.             if(ds.find(i)==i) ans = max(ans, ds.sz[i]);
  71.         }
  72.         cout << ans << "\n";
  73.     }
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
6
3
000
4
0010
7
1011001
4
0001
2
11
1
0
stdout
copy 
3
9
10
7
1
0
https://ideone.com/GZLkl8
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!