oj.uz

Submission #144986

# Submission time Handle Problem Language Result Execution time Memory
144986 2019-08-18T10:20:34 Z Abelyan Raspad (COI17_raspad) C++17
26 / 100
 6000 ms 162396 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa

const int N=5e6+10;
const ll MOD2=998244353;
const ll MOD=1e9+7;

int par[N],sz[N];
ll qan;

void make(int v){
    par[v]=v;
    sz[v]=1;
    qan++;
}

int get(int v){
    if (par[v]==v)return v;
    return par[v]=get(par[v]);
}

void unite(int a,int b){
    a=get(a);
    b=get(b);
    if (a!=b){
        if (sz[a]<sz[b])swap(a,b);
        par[b]=a;
        sz[a]+=sz[b];
        qan--;
    }
}

string c[N];
ll ans=0;
int main(){
    fastio;
    srng;
    #ifdef ALEXPC
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    cin>>n>>m;
    FOR(i,n){
        cin>>c[i];
    }
    FOR(sk,n){
        qan=0;
        FORT(i,sk,n-1){
            //cout<<1<<endl;
            FOR(j,m){
                //cout<<2<<endl;
                if (c[i][j]=='1'){
                    make(i*m+j);
                    //cout<<sk<<" "<<i<<" "<<j<<" "<<qan<<endl;
                    if (i!=sk && c[i-1][j]=='1')unite(i*m+j,(i-1)*m+j);
                    //cout<<sk<<" "<<i<<" "<<j<<" "<<qan<<endl;
                    if (j!=0 && c[i][j-1]=='1')unite(i*m+j,i*m+j-1);
                    //cout<<sk<<" "<<i<<" "<<j<<" "<<qan<<endl;
                }
                
                //cout<<qan<<endl;
            }
            //cout<<sk<<" "<<i<<" "<<qan<<endl;
            ans+=qan;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 156944 KB Output is correct
2 Correct 147 ms 157008 KB Output is correct
3 Correct 147 ms 156920 KB Output is correct
4 Correct 146 ms 156920 KB Output is correct
5 Correct 146 ms 156920 KB Output is correct
6 Correct 146 ms 156952 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 156944 KB Output is correct
2 Correct 147 ms 157008 KB Output is correct
3 Correct 147 ms 156920 KB Output is correct
4 Correct 146 ms 156920 KB Output is correct
5 Correct 146 ms 156920 KB Output is correct
6 Correct 146 ms 156952 KB Output is correct
7 Correct 318 ms 157236 KB Output is correct
8 Correct 144 ms 156920 KB Output is correct
9 Correct 586 ms 157436 KB Output is correct
10 Correct 249 ms 157304 KB Output is correct
11 Correct 419 ms 157432 KB Output is correct
12 Correct 206 ms 157176 KB Output is correct
13 Correct 347 ms 157436 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6088 ms 162396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 156944 KB Output is correct
2 Correct 147 ms 157008 KB Output is correct
3 Correct 147 ms 156920 KB Output is correct
4 Correct 146 ms 156920 KB Output is correct
5 Correct 146 ms 156920 KB Output is correct
6 Correct 146 ms 156952 KB Output is correct
7 Correct 318 ms 157236 KB Output is correct
8 Correct 144 ms 156920 KB Output is correct
9 Correct 586 ms 157436 KB Output is correct
10 Correct 249 ms 157304 KB Output is correct
11 Correct 419 ms 157432 KB Output is correct
12 Correct 206 ms 157176 KB Output is correct
13 Correct 347 ms 157436 KB Output is correct
14 Execution timed out 6088 ms 162396 KB Time limit exceeded
15 Halted 0 ms 0 KB -