글 읽기 - k<size-1과 k+1<size의 차이

leinad2 3년 전 1

IOI 2020 day 1 2번 connecting supertrees를 풀었는데, 75번째 줄의 주석친 부분 k+1<B[A[i][j]].size()를 k<B[A[i][j]].size()-1로 고치면 원래 100점이었는데 갑자기 23점으로 바뀝니다. 아무리 봐도 두 식이 똑같은 줄 알았는데, 두 식의 차이점이 무엇인가요...?

#include "supertrees.h"
#include <vector>

using namespace std;
int par[1010], i, j, k;
int Find(int v)
{
	if(v==par[v])return v;
	int q=Find(par[v]);
	par[v]=q;
	return q;
}
int construct(vector<vector<int> > p) {
	int n=p.size();
	vector<vector<int> >ans;
	for(i=0;i<n;i++)
	{
		vector<int>row;
		row.resize(n);
		ans.push_back(row);
	}
	for(i=0;i<n;i++)par[i]=i;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(p[i][j]==3)return 0;
			if(p[i][j])
			{
				par[Find(i)]=Find(j);
			}
		}
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(!p[i][j]&&Find(i)==Find(j))return 0;
		}
	}
	vector<int>A[1010], B[1010];
	for(i=0;i<n;i++)
	{
		A[Find(i)].push_back(i);
	}
	for(i=0;i<n;i++)par[i]=i;
	for(i=0;i<n;i++)
	{
		for(j=0;j<A[i].size();j++)
		{
			for(k=0;k<A[i].size();k++)
			{
				if(p[A[i][j]][A[i][k]]==1)
				{
					par[Find(A[i][j])]=Find(A[i][k]);
				}
			}
		}
		for(j=0;j<A[i].size();j++)
		{
			for(k=0;k<A[i].size();k++)
			{
				if(p[A[i][j]][A[i][k]]==2&&Find(A[i][j])==Find(A[i][k]))
				{
					return 0;
				}
			}
		}
		for(j=0;j<A[i].size();j++)
		{
			B[Find(A[i][j])].push_back(A[i][j]);
		}
		for(j=0;j<A[i].size();j++)
		{
			for(k=0;k+1<B[A[i][j]].size();k++)//이걸 k<B[A[i][j]].size()-1로 고치면 23점으로 변함
			{
				ans[B[A[i][j]][k]][B[A[i][j]][k+1]]=ans[B[A[i][j]][k+1]][B[A[i][j]][k]]=1;
			}
		}
		vector<int>v;
		for(j=0;j<A[i].size();j++)
		{
			if(B[A[i][j]].size())
			{
				v.push_back(B[A[i][j]][0]);
			}
		}
		if(v.size()==2)return 0;
		else if(v.size()>=3)
		{
			for(j=0;j<v.size()-1;j++)
			{
				ans[v[j]][v[j+1]]=ans[v[j+1]][v[j]]=1;
			}
			ans[v[0]][v.back()]=ans[v.back()][v[0]]=1;
		}
	}
	build(ans);
	return 1;
}

leinad2 3년 전 3

슬랙에서 해결해주셨습니다. 감사합니다!

djm03178

2:15 PM
size()는 unsigned 정수를 반환하기 때문에 0이 반환되었을 때 1을 빼면 오버플로가 발생합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

k<size-1과 k+1<size의 차이

leinad2 3년 전 1

leinad2 3년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말