제출 #199812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
199812		mohammedehab2002	Sajam (COCI18_sajam)	C++11	45 / 90	96 ms	3324 KiB

sajam

#include <bits/stdc++.h>
using namespace std;
pair<int,int> par[2005];
string s[1005];
pair<int,int> find(pair<int,int> x)
{
	if (par[x.first]==x)
	return x;
	auto p=find(par[x.first]);
	p.second^=par[x.first].second;
	return par[x.first]=p;
}
int Union(int x,int y,int a)
{
	auto xx=find({x,0}),yy=find({y,0});
	if (xx.first==yy.first)
	return ((xx.second^yy.second)!=a);
	par[xx.first]={yy.first,(a^xx.second^yy.second)};
	return 0;
}
int main()
{
	int n,k;
	cin >> n >> k;
	for (int i=0;i<2*n;i++)
	par[i]={i,0};
	for (int i=0;i<n;i++)
	{
		cin >> s[i];
		for (int j=0;j<n;j++)
		k-=Union(i,j+n,s[i][j]=='o');
	}
	printf(k>=0? "DA":"NE");
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 15