| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 232832 |
2020-05-18T10:31:34 Z |
shayan_p |
Raspad (COI17_raspad) |
C++14 |
|
6000 ms |
220736 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 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;*/
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
10752 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
11008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
10752 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
11008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6067 ms |
220736 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
10752 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
11008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
