oj.uz

Submission #232845

# Submission time Handle Problem Language Result Execution time Memory
232845 2020-05-18T10:59:29 Z shayan_p Raspad (COI17_raspad) C++14
26 / 100
 6000 ms 220796 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], col[66], colId;
ll _MSK;
 
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;    
}
 
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;
	ans+= num;
	for(int r = l+1; r < n; r++){
	    for(int i = 0; i < comp; i++)
		if((vec[r-1][comp][i] & MSK[r]) != 0)
		    num--;
	    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;    
    */


    for(int l = 0; l < n; l++){
	int num = 0, comp = 0;
	for(int r = l; r < n; r++){
	    if(l != r){
		for(int i = 0; i < comp; i++)
		    if((vec[r-1][comp][i] & MSK[r]) != 0)
			num--;
	    }
	    comp = -1;
	    for(int i = MAX-1; i >= 0; i--)
		if(ID[r][i] >= l)
		    comp = i;
	    num+= comp;
	    ans+= num;
	}
    }
    return cout << ans << endl, 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10752 KB Output is correct
2 Correct 10 ms 11008 KB Output is correct
3 Correct 9 ms 11008 KB Output is correct
4 Correct 10 ms 11008 KB Output is correct
5 Correct 10 ms 11008 KB Output is correct
6 Correct 11 ms 11136 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10752 KB Output is correct
2 Correct 10 ms 11008 KB Output is correct
3 Correct 9 ms 11008 KB Output is correct
4 Correct 10 ms 11008 KB Output is correct
5 Correct 10 ms 11008 KB Output is correct
6 Correct 11 ms 11136 KB Output is correct
7 Correct 29 ms 14336 KB Output is correct
8 Correct 15 ms 12672 KB Output is correct
9 Correct 38 ms 15616 KB Output is correct
10 Correct 31 ms 15232 KB Output is correct
11 Correct 34 ms 15232 KB Output is correct
12 Correct 21 ms 14592 KB Output is correct
13 Correct 30 ms 15096 KB Output is correct

Subtask #3
0 / 35.0

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

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10752 KB Output is correct
2 Correct 10 ms 11008 KB Output is correct
3 Correct 9 ms 11008 KB Output is correct
4 Correct 10 ms 11008 KB Output is correct
5 Correct 10 ms 11008 KB Output is correct
6 Correct 11 ms 11136 KB Output is correct
7 Correct 29 ms 14336 KB Output is correct
8 Correct 15 ms 12672 KB Output is correct
9 Correct 38 ms 15616 KB Output is correct
10 Correct 31 ms 15232 KB Output is correct
11 Correct 34 ms 15232 KB Output is correct
12 Correct 21 ms 14592 KB Output is correct
13 Correct 30 ms 15096 KB Output is correct
14 Execution timed out 6083 ms 220796 KB Time limit exceeded
15 Halted 0 ms 0 KB -