Submission #26337

#	Time	Username	Problem	Language	Result	Execution time	Memory
26337		suhgyuho_william	Raspad (COI17_raspad)	C++14	0 / 100	129 ms	59668 KiB

raspad

#include <bits/stdc++.h>

#define lld long long
#define pp pair<int,int>
#define pb push_back
#define MOD 1000000007
#define left lleft
#define right rright
#define Inf 2000000000
#define Linf 1000000000000000000LL
#define next nnext
#define minus mminus

using namespace std;

int N,M,nn; lld ans,sum;
int a[100002][52];
int where[100002][52];
int **when[100002];
char s[100];
int par[100];

int getpar(int x){
	if(x == par[x]) return x;
	return par[x] = getpar(par[x]);
}
void merge(int x,int y){
	x = getpar(x);  y = getpar(y);
	par[x] = y;
}
void update(int node,int l,int r,lld s,lld e,lld value){
    if(s > e) return;
	sum += (e-s+1)*value;
}

int main(){
    //freopen("input.txt","r",stdin);
	scanf("%d %d",&N,&M);
	for(nn=1; nn<N; nn*=2);
	for(int i=1; i<=N; i++){
		scanf("%s",s);
		for(int j=1; j<=M; j++) a[i][j] = s[j-1]-'0';
	}
	for(int i=1; i<=N; i++){
		vector<pp> tmp;
		bool flag = false;
		for(int j=1; j<=M+1; j++){
			if(!flag && a[i][j] == 1){
				flag = true;
				tmp.pb({j,0});
			}
			if(flag && a[i][j] == 0){
				flag = false;
				tmp.back().second = j-1;
			}
		}
		update(1,1,nn,i,i,tmp.size());
		vector<pp> memo;
		for(int j=0; j<tmp.size(); j++){
			int s,e;
			s = tmp[j].first; e = tmp[j].second;
			vector<int> t;
			for(int k=s; k<=e; k++){
				where[i][k] = j;
				if(a[i-1][k] == 1){
					if(t.size() == 0) t.pb(where[i-1][k]);
					else if(t.back() != where[i-1][k]) t.pb(where[i-1][k]);
				}
			}
			if(t.size() == 0){
				memo.pb({0,-1});
				update(1,1,nn,1,i-1,1);
			}else{
				memo.pb({t[0],t.back()});
				vector<pair<int,pp>> calc;
				for(int k=0; k<t.size(); k++) par[k] = k;
				for(int k=0; k<(int)t.size()-1; k++){
					for(int it=k+1; it<t.size(); it++){
						calc.pb({when[i-1][t[k]][t[it]],{k,it}});
					}
				}
				sort(calc.begin(),calc.end());
				reverse(calc.begin(),calc.end());
				for(auto &k : calc){
					int x,y,z;
					x = k.second.first; y = k.second.second;
					z = k.first;
					if(getpar(x) == getpar(y)) continue;
					update(1,1,nn,z+1,i-1,-1);
					merge(x,y);
				}
			}
		}
		when[i] = (int**)malloc(sizeof(int*)*tmp.size());
		for(int j=0; j<tmp.size(); j++){
			when[i][j] = (int*)malloc(sizeof(int)*tmp.size());
			when[i][j][j] = i;
			for(int k=j+1; k<tmp.size(); k++){
				when[i][j][k] = 0;
				for(int t1 = memo[j].first; t1 <= memo[j].second; t1++){
					for(int t2 = memo[k].first; t2 <= memo[k].second; t2++){
						when[i][j][k] = max(when[i][j][k],when[i-1][t1][t2]);
					}
				}
			}
		}
		ans += sum;
	}
	printf("%lld\n",ans);

	return 0;
}

Compilation message (stderr)

raspad.cpp: In function 'int main()':
raspad.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<tmp.size(); j++){
                 ^
raspad.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0; k<t.size(); k++) par[k] = k;
                   ^
raspad.cpp:78:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int it=k+1; it<t.size(); it++){
                        ^
raspad.cpp:95:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<tmp.size(); j++){
                 ^
raspad.cpp:98:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=j+1; k<tmp.size(); k++){
                    ^
raspad.cpp:38:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^
raspad.cpp:41:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s);
                ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 17
• Subtask 3: 0 / 35
• Subtask 4: 0 / 39