Submission #350534

#	Time	Username	Problem	Language	Result	Execution time	Memory
350534		arnold518	Raspad (COI17_raspad)	C++14	0 / 100	6042 ms	32364 KiB

raspad

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 1e5;
const int MAXM = 50;
 
int N, M;
int A[MAXN+10][MAXM+10];
vector<pii> R[MAXN+10];
 
struct UF
{
	int par[MAXM*2+10];
	void init()
	{
		for(int i=1; i<=M+M; i++) par[i]=i;
	}
	int Find(int x)
	{
		if(x>M+M) while(1);
		if(x==par[x]) return x;
		return par[x]=Find(par[x]);
	}
	void Union(int x, int y)
	{
		//if(x>M+M) while(1);
		//if(y>M+M) while(1);
		x=Find(x); y=Find(y);
		if(x==y) return;
		if(x>y) swap(x, y);
		par[x]=y;
	}
}uf;
 
ll ans=0;
 
int main()
{
	srand(time(NULL));
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++)
	{
		scanf("%1d", &A[i][j]);
		//A[i][j]=rand()%2;
	}
 
	for(int i=1; i<=N; i++)
	{
		R[i].push_back({0, 0});
 
		int l, r;
		int cnt=1;
		for(int j=1; j<=M; j++)
		{
			if(!A[i][j-1] && A[i][j]) l=j;
			if(A[i][j] && !A[i][j+1])
			{
				r=j;
				R[i].push_back({l, r});
				for(int k=l; k<=r; k++) A[i][k]=cnt;
				if(cnt>M) while(1);
				cnt++;
			}
		}
	}
 
	ll val=0;
	vector<pair<int, pii>> V;
 
 
	for(int i=1; i<=N; i++)
	{
		vector<pair<int, pii>> V2;
 
		uf.init();
		for(int k=1; k<R[i].size(); k++)
		{
			int l=R[i][k].first, r=R[i][k].second;
			vector<int> t;
			for(int j=l; j<=r; j++)
			{
				if(A[i-1][j]) t.push_back(A[i-1][j]);
			}
			if(t.empty()) continue;
			t.erase(unique(t.begin(), t.end()), t.end());
			for(int j=1; j<t.size(); j++)
			{
				assert(t[0]<=M+M);
				assert(t[j]<=M+M);
				if(uf.Find(t[0])!=uf.Find(t[j]))
				{
					uf.Union(t[0], t[j]);
					val-=i-1;
				}
			}
		}
 
		for(auto it : V)
		{
			assert(it.second.first<=M+M);
			assert(it.second.second<=M+M);
			if(uf.Find(it.second.first)==uf.Find(it.second.second))
			{
				val+=it.first;
			}
			else
			{
				uf.Union(it.second.first, it.second.second);
			}
		}
		//printf("!%lld\n", val);
 
		val+=R[i].size()-1;
		for(int k=1; k<R[i].size(); k++)
		{
			int l=R[i][k].first, r=R[i][k].second;
			bool flag=true;
			for(int j=l; j<=r; j++)
			{
				if(A[i-1][j]) flag=false;
			}
			if(flag) val+=i-1;
		}
		uf.init();
		for(int k=1; k<R[i-1].size(); k++)
		{
			int l=R[i-1][k].first, r=R[i-1][k].second;
			vector<int> t;
			for(int j=l; j<=r; j++)
			{
				if(A[i][j]) t.push_back(A[i][j]);
			}
			if(t.empty()) continue;
			t.erase(unique(t.begin(), t.end()), t.end());
			for(int j=0; j<t.size(); j++)
			{
				uf.Union(k, t[j]+M);
			}
			for(int j=1; j<t.size(); j++)
			{
				V2.push_back({i-1, {t[0], t[j]}});
			}
		}
 
		for(auto it : V)
		{
			assert(it.second.first<=M+M);
			assert(it.second.second<=M+M);
			if(uf.Find(it.second.first)!=uf.Find(it.second.second))
			{
				if(uf.Find(it.second.first)>M && uf.Find(it.second.second)>M)
				{
					V2.push_back({it.first, {it.second.first-M, it.second.second-M}});
					uf.Union(it.second.first, it.second.second);
				}
			}
		}
		V=V2;
		ans+=val;
		//printf("%lld\n", val);
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

raspad.cpp: In function 'int main()':
raspad.cpp:80:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for(int k=1; k<R[i].size(); k++)
      |                ~^~~~~~~~~~~~
raspad.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |    for(int j=1; j<t.size(); j++)
      |                 ~^~~~~~~~~
raspad.cpp:118:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |   for(int k=1; k<R[i].size(); k++)
      |                ~^~~~~~~~~~~~
raspad.cpp:129:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |   for(int k=1; k<R[i-1].size(); k++)
      |                ~^~~~~~~~~~~~~~
raspad.cpp:139:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |    for(int j=0; j<t.size(); j++)
      |                 ~^~~~~~~~~
raspad.cpp:143:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |    for(int j=1; j<t.size(); j++)
      |                 ~^~~~~~~~~
raspad.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
raspad.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |   scanf("%1d", &A[i][j]);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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