oj.uz

Submission #232836

# Submission time Handle Problem Language Result Execution time Memory
232836 2020-05-18T10:43:46 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 12 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 12 ms 11008 KB Output is correct
6 Correct 12 ms 11008 KB Output is correct
7 Correct 193 ms 14336 KB Output is correct
8 Correct 23 ms 12672 KB Output is correct
9 Correct 458 ms 15608 KB Output is correct
10 Correct 135 ms 15232 KB Output is correct
11 Correct 276 ms 15200 KB Output is correct
12 Correct 97 ms 14456 KB Output is correct
13 Correct 254 ms 15096 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6074 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 12 ms 11008 KB Output is correct
6 Correct 12 ms 11008 KB Output is correct
7 Correct 193 ms 14336 KB Output is correct
8 Correct 23 ms 12672 KB Output is correct
9 Correct 458 ms 15608 KB Output is correct
10 Correct 135 ms 15232 KB Output is correct
11 Correct 276 ms 15200 KB Output is correct
12 Correct 97 ms 14456 KB Output is correct
13 Correct 254 ms 15096 KB Output is correct
14 Execution timed out 6074 ms 220792 KB Time limit exceeded
15 Halted 0 ms 0 KB -