oj.uz

Submission #232831

# Submission time Handle Problem Language Result Execution time Memory
232831 2020-05-18T10:26:27 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], _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 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;
	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 10624 KB Output is correct
2 Correct 30 ms 11008 KB Output is correct
3 Correct 11 ms 11008 KB Output is correct
4 Correct 77 ms 11008 KB Output is correct
5 Correct 25 ms 11008 KB Output is correct
6 Correct 31 ms 10880 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10624 KB Output is correct
2 Correct 30 ms 11008 KB Output is correct
3 Correct 11 ms 11008 KB Output is correct
4 Correct 77 ms 11008 KB Output is correct
5 Correct 25 ms 11008 KB Output is correct
6 Correct 31 ms 10880 KB Output is correct
7 Correct 1981 ms 14368 KB Output is correct
8 Correct 19 ms 12672 KB Output is correct
9 Correct 1935 ms 14840 KB Output is correct
10 Correct 4775 ms 14312 KB Output is correct
11 Correct 1714 ms 14840 KB Output is correct
12 Correct 214 ms 13824 KB Output is correct
13 Correct 1709 ms 14328 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6071 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 10624 KB Output is correct
2 Correct 30 ms 11008 KB Output is correct
3 Correct 11 ms 11008 KB Output is correct
4 Correct 77 ms 11008 KB Output is correct
5 Correct 25 ms 11008 KB Output is correct
6 Correct 31 ms 10880 KB Output is correct
7 Correct 1981 ms 14368 KB Output is correct
8 Correct 19 ms 12672 KB Output is correct
9 Correct 1935 ms 14840 KB Output is correct
10 Correct 4775 ms 14312 KB Output is correct
11 Correct 1714 ms 14840 KB Output is correct
12 Correct 214 ms 13824 KB Output is correct
13 Correct 1709 ms 14328 KB Output is correct
14 Execution timed out 6071 ms 220792 KB Time limit exceeded
15 Halted 0 ms 0 KB -