oj.uz

답안 #232833

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
232833 2020-05-18T10:34: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;
	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);
	    MRG(v2, v);
	    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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10752 KB Output is correct
2 Correct 16 ms 11008 KB Output is correct
3 Correct 12 ms 11008 KB Output is correct
4 Correct 15 ms 11008 KB Output is correct
5 Correct 14 ms 11008 KB Output is correct
6 Correct 15 ms 11008 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10752 KB Output is correct
2 Correct 16 ms 11008 KB Output is correct
3 Correct 12 ms 11008 KB Output is correct
4 Correct 15 ms 11008 KB Output is correct
5 Correct 14 ms 11008 KB Output is correct
6 Correct 15 ms 11008 KB Output is correct
7 Correct 458 ms 14432 KB Output is correct
8 Correct 29 ms 12672 KB Output is correct
9 Correct 829 ms 14740 KB Output is correct
10 Correct 382 ms 14328 KB Output is correct
11 Correct 593 ms 14812 KB Output is correct
12 Correct 234 ms 13824 KB Output is correct
13 Correct 504 ms 14456 KB Output is correct

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6063 ms 220792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10752 KB Output is correct
2 Correct 16 ms 11008 KB Output is correct
3 Correct 12 ms 11008 KB Output is correct
4 Correct 15 ms 11008 KB Output is correct
5 Correct 14 ms 11008 KB Output is correct
6 Correct 15 ms 11008 KB Output is correct
7 Correct 458 ms 14432 KB Output is correct
8 Correct 29 ms 12672 KB Output is correct
9 Correct 829 ms 14740 KB Output is correct
10 Correct 382 ms 14328 KB Output is correct
11 Correct 593 ms 14812 KB Output is correct
12 Correct 234 ms 13824 KB Output is correct
13 Correct 504 ms 14456 KB Output is correct
14 Execution timed out 6063 ms 220792 KB Time limit exceeded
15 Halted 0 ms 0 KB -