oj.uz

Submission #232828

# Submission time Handle Problem Language Result Execution time Memory
232828 2020-05-18T10:11:42 Z shayan_p Raspad (COI17_raspad) C++14
26 / 100
 6000 ms 11648 KB 
// Never let them see you bleed...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e5 + 10, MAX = 26, mod = 1e9 + 7, inf = 1e9 + 10;

ll MSK[maxn];
ll vec[maxn][MAX][MAX], arr[MAX];
int ID[maxn][MAX];

int n, m;

int origin(int i){ ///////
    ll msk = 0;
    int cnt = 0;
    for(int j = 0; j < m; j++){
	if(bit(MSK[i], j))
	    msk|= 1ll<<j;
	if(bit(MSK[i], j) && !bit(MSK[i], j+1))
	    arr[cnt++] = msk, msk = 0;
    }
    memcpy(vec[i][cnt], arr, sizeof arr);
    ID[i][cnt] = i;

    return cnt;
}

int aft[66], bef[66], _MSK, col[66], colId;

void dfs(int u){
    col[u] = colId;
    arr[colId]|= 1ll<<u;
    if(bef[u] != -1 && col[bef[u]] == -1)
	dfs(bef[u]);
    if(aft[u] != -1 && col[aft[u]] == -1)
	dfs(aft[u]);
    if(u != 0 && bit(_MSK, u-1) && col[u-1] == -1)
	dfs(u-1);
    if(bit(_MSK, u+1) && col[u+1] == -1)
	dfs(u+1);
}

int mrg(int id, ll *ARR, int SZ, int _ID){ //////
    memset(aft, -1, sizeof aft);
    memset(bef, -1, sizeof bef);
    memset(col, -1, sizeof col);
    memset(arr, 0, sizeof arr);    
    colId = 0;
    _MSK = MSK[id];    
    for(int i = 0; i < SZ; i++){
	ll msk = MSK[id] & ARR[i];
	int bf = -1;
	while(msk){
	    int nw = __builtin_ctzll(msk);
	    msk^= 1ll<<nw;
	    if(bf != -1)
		bef[nw] = bf, aft[bf] = nw;
	    bf = nw;
	}
    }
    for(int i = 0; i < m; i++){
	if(col[i] == -1 && bit(_MSK, i)){
	    dfs(i);
	    colId++;
	}		    
    }
    if(ID[id][colId] == -1){
	ID[id][colId] = _ID;
	memcpy(vec[id][colId], arr, sizeof arr);
    }

    return colId;    
}




void MRG(vector<ll> &v, ll msk){
    int msk2 = 0;
    for(int i = 0; i < sz(v); i++){
	if(msk & v[i])
	    msk2|= 1<<i;
    }
    vector<ll> ans;
    ll _ans = 0;
    for(int i = 0; i < sz(v); i++){
	if(bit(msk2, i))
	    _ans|= v[i];
	else
	    ans.PB(v[i]);
    }
    if(_ans != 0)
	ans.PB(_ans);
    v = ans;
}

void ORIG(vector<ll>&v, int l){
    ll _msk = 0;
    for(int i = 0; i < m; i++){
	if(bit(MSK[l], i))
	    _msk|= 1ll<<i;
	if(bit(MSK[l], i) && !bit(MSK[l], i+1))
	    v.PB(_msk), _msk = 0;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    memset(ID, -1, sizeof ID);
    
    cin >> n >> m;
    for(int i = 0; i < n; i++){
	string s;
	cin >> s;
	for(int j = 0; j < m; j++)
	    MSK[i]|= (1ll * (s[j] == '1')) << j;
    }

    ll ans = 0;
    for(int l = 0; l < n; l++){
	//	int num = origin(l), comp = num;
	vector<ll> v;	
	ORIG(v, l);
	int num = sz(v);
	ans+= num;
	for(int r = l+1; r < n; r++){
	    for(ll x : v)
		if((x & MSK[r]) != 0)
		    num--;
	    vector<ll> v2;
	    ORIG(v2, r);
	    for(ll x : v)
		MRG(v2, x);
	    num+= sz(v2);
	    ans+= num;
	    v = v2;
	    /*
	    comp = mrg(r, vec[r-1][comp], comp, 0);
	    num+= comp;
	    ans+= num;*/	    
	}
    }
    return cout << ans << endl, 0;
    
    /*
    origin(0);
    for(int i = 1; i < n; i++){
	origin(i);
	for(int j = MAX-1; j >= 0; j--){
	    if(ID[i-1][j] == -1)
		continue;
	    mrg(i, vec[i-1][j], j, ID[i-1][j]);	    
	}
    }
    ll ans = 0;
    for(int i = 0; i < n; i++){
	if(MSK[i] == 0)
	    continue;
	for(int j = MAX-1; j > 0; j--){
	    if(ID[i][j] == -1)
		continue;
	    for(int k = 0; k < j; k++){
		int cof = 1;
		if((MSK[i+1] & vec[i][j][k]) == 0)
		    cof = n-i;
		ans+= 1ll * cof * (ID[i][j] - ID[i][j-1]);
	    }
	}
    }
    return cout << ans << endl, 0;*/
    
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10496 KB Output is correct
2 Correct 38 ms 10496 KB Output is correct
3 Correct 11 ms 10496 KB Output is correct
4 Correct 79 ms 10616 KB Output is correct
5 Correct 25 ms 10496 KB Output is correct
6 Correct 32 ms 10496 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10496 KB Output is correct
2 Correct 38 ms 10496 KB Output is correct
3 Correct 11 ms 10496 KB Output is correct
4 Correct 79 ms 10616 KB Output is correct
5 Correct 25 ms 10496 KB Output is correct
6 Correct 32 ms 10496 KB Output is correct
7 Correct 2017 ms 10744 KB Output is correct
8 Correct 17 ms 10496 KB Output is correct
9 Correct 1991 ms 10744 KB Output is correct
10 Correct 4797 ms 10624 KB Output is correct
11 Correct 1763 ms 10636 KB Output is correct
12 Correct 205 ms 10624 KB Output is correct
13 Correct 1704 ms 10744 KB Output is correct

Subtask #3
0 / 35.0

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

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10496 KB Output is correct
2 Correct 38 ms 10496 KB Output is correct
3 Correct 11 ms 10496 KB Output is correct
4 Correct 79 ms 10616 KB Output is correct
5 Correct 25 ms 10496 KB Output is correct
6 Correct 32 ms 10496 KB Output is correct
7 Correct 2017 ms 10744 KB Output is correct
8 Correct 17 ms 10496 KB Output is correct
9 Correct 1991 ms 10744 KB Output is correct
10 Correct 4797 ms 10624 KB Output is correct
11 Correct 1763 ms 10636 KB Output is correct
12 Correct 205 ms 10624 KB Output is correct
13 Correct 1704 ms 10744 KB Output is correct
14 Execution timed out 6059 ms 11648 KB Time limit exceeded
15 Halted 0 ms 0 KB -