Submission #26327

#	Time	Username	Problem	Language	Result	Execution time	Memory
26327		khsoo01	Raspad (COI17_raspad)	C++11	100 / 100	199 ms	87076 KiB

raspad

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll,ll> tp;
const ll N = 100005, M = 55;

ll n, m, ans[N], par[M], b[2][M], cc, ic, uc, cnt;
char ipt[N][M];

vector<tp> qry[N];

void parse (char I[], ll B[]) {
	for(ll i=1;i<=m;i++) {
		if(I[i] == '1') {
			if(I[i-1] != '1') cc++;
			B[i] = cc;
		}
		else B[i] = 0;
	}
}

ll Find (ll P) {
	if(par[P] == P) return P;
	return par[P] = Find(par[P]);
}

void Union (ll A, ll B, vector<tp> &V) {
	A = Find(A); B = Find(B);
	if(A == B) return;
	if(A > B) swap(A, B);
	par[B] = A;
	cc--;
	if(A <= ic && B <= ic) {
		V.push_back(tp(A, B, cnt));
		cnt = 0;
	}
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++) {
		scanf("%s",ipt[i]+1);
	}
	for(ll i=1;i<=n;i++) {
		cc = 0; cnt = 1;
		parse(ipt[i], b[1]);
		ans[i] = ans[i-1] + cc; ic = cc;
		if(i == 1) continue;
		parse(ipt[i-1], b[0]);
		ll lft = i-1; uc = cc - ic;
		for(ll j=1;j<=cc;j++) par[j] = j;
		for(ll j=1;j<=m;j++) {
			ll A = b[0][j], B = b[1][j];
			if(A && B) Union(A, B, qry[i]);
		}
		for(auto &T : qry[i-1]) {
			ll A, B, C; tie(A, B, C) = T;
			ans[i] += C * (cc - uc);
			uc--; lft -= C; cnt += C;
			Union(A+ic, B+ic, qry[i]);
		}
		ans[i] += lft * (cc - uc);
	}
	ll sum = 0;
	for(ll i=1;i<=n;i++) sum += ans[i];
	printf("%lld\n",sum);
}

Compilation message (stderr)

raspad.cpp: In function 'int main()':
raspad.cpp:41:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&m);
                         ^
raspad.cpp:43:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",ipt[i]+1);
                       ^

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