oj.uz

Submission #232841

# Submission time Handle Problem Language Result Execution time Memory
232841 2020-05-18T10:48:41 Z shayan_p Raspad (COI17_raspad) C++14
26 / 100
 6000 ms 220792 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;    
}
 
 
 
 
/*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 MRG(vector<ll> &A, vector<ll>&B){
    memset(aft, -1, sizeof aft);
    memset(bef, -1, sizeof bef);
    memset(col, -1, sizeof col);
    memset(arr, 0, sizeof arr);    
    colId = 0;
    _MSK = 0;
    for(ll x : A)
	_MSK|= x;
    for(int i = 0; i < sz(B); i++){
	ll msk = _MSK & B[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++;
	}		    
    }
    A.clear();
    A.resize(colId);
    for(ll x : A)
	assert(x == 0);
    for(int i = 0; i < colId; i++)
	A[i] = arr[i];
}
 
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 cnt = origin(l);
    for(int i = 0; i < cnt; i++)
	v.PB(vec[l][cnt][i]);
}
 
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;*/
    
}

Subtask #1
9.0 / 9.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10752 KB Output is correct
2 Correct 13 ms 11008 KB Output is correct
3 Correct 11 ms 10880 KB Output is correct
4 Correct 12 ms 11008 KB Output is correct
5 Correct 11 ms 11008 KB Output is correct
6 Correct 12 ms 11008 KB Output is correct
7 Correct 197 ms 14336 KB Output is correct
8 Correct 27 ms 12800 KB Output is correct
9 Correct 451 ms 15608 KB Output is correct
10 Correct 130 ms 15232 KB Output is correct
11 Correct 285 ms 15280 KB Output is correct
12 Correct 101 ms 14456 KB Output is correct
13 Correct 249 ms 14968 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6116 ms 220792 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 10752 KB Output is correct
2 Correct 13 ms 11008 KB Output is correct
3 Correct 11 ms 10880 KB Output is correct
4 Correct 12 ms 11008 KB Output is correct
5 Correct 11 ms 11008 KB Output is correct
6 Correct 12 ms 11008 KB Output is correct
7 Correct 197 ms 14336 KB Output is correct
8 Correct 27 ms 12800 KB Output is correct
9 Correct 451 ms 15608 KB Output is correct
10 Correct 130 ms 15232 KB Output is correct
11 Correct 285 ms 15280 KB Output is correct
12 Correct 101 ms 14456 KB Output is correct
13 Correct 249 ms 14968 KB Output is correct
14 Execution timed out 6116 ms 220792 KB Time limit exceeded
15 Halted 0 ms 0 KB -