제출 #640267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640267		ggoh	도시들 (IOI15_towns)	C++14	48 / 100	21 ms	468 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int>pii;

int dis[111][111],par[111],wei[111];
int find(int p)
{
	if(par[p]==p)return p;
	else return par[p]=find(par[p]);
}
void uni(int p,int q)
{
	p=find(p);q=find(q);
	if(p==q)return ;
	wei[q]+=wei[p];
	par[p]=q;
}
int ch,n;
struct tri{
	int a,b,c;
};
bool cmp(tri A, tri B){return A.a<B.a;}
vector<tri>X;
void f(int r)
{
	vector<pii>C;
	int cnt0=1,cnt1=1,check=0;
	for(auto &k:X)
	{
		if(k.a==r)C.push_back({k.b,k.c});
		else if(k.a<r)cnt0++;
		else cnt1++;
	}
	for(auto &k:C)
	{
		par[k.second]=k.second;
		wei[k.second]=1;
	}
	for(int i=0;i<sz(C);i++)
	{
		for(int j=i+1;j<sz(C);j++)
		{
			if(dis[C[i].second][C[j].second]!=C[i].first+C[j].first)uni(C[i].second,C[j].second);
		}
	}
	for(auto &k:C)
	{
		if(wei[k.second]>n/2)check=1;
	}
	if(cnt0>n/2 || cnt1>n/2)check=1;
	if(!check)ch=1;
}
int hubDistance(int N, int sub) {
	if(sub==1 || sub==3){
	int maxi=-1,maxj=-1,maxx=-1;
	int R=1e9;
	for(int i=0;i<N;i++)
	{
		for(int j=i+1;j<N;j++)
		{
			dis[i][j]=dis[j][i]=getDistance(i,j);
		}
	}
	n=N;
	for(int i=1;i<N;i++)
	{
		if(dis[0][i]>maxx)
		{
			maxx=dis[0][i];
			maxi=i;
		}
	}
	maxx=-1;
	for(int i=0;i<N;i++)
	{
		if(i!=maxi)
		{
			if(dis[maxi][i]>maxx)
			{
				maxx=dis[maxi][i];
				maxj=i;
			}
		}
	}
	X.clear();
	for(int i=0;i<N;i++)
	{
		if(i!=maxi && i!=maxj)
		{
			X.push_back({(dis[maxi][i]-dis[maxj][i]+maxx)/2,(dis[maxi][i]+dis[maxj][i]-maxx)/2,i});
		}
	}
	sort(X.begin(),X.end(),cmp);
	for(auto &k:X)
	{
		R=min(R,max(maxx-k.a,k.a));
	}
	ch=-1;
	f(R);
	f(maxx-R);

	return ch*R;
	}
	else
	{
		int maxi=-1,maxj=-1,maxx=-1;
	int R=1e9;
	for(int i=1;i<N;i++)
	{
		dis[0][i]=dis[i][0]=getDistance(0,i);
		if(dis[0][i]>maxx)
		{
			maxx=dis[0][i];
			maxi=i;
		}
	}
	maxx=-1;
	for(int i=0;i<N;i++)
	{
		if(i!=maxi)
		{
			dis[maxi][i]=dis[i][maxi]=getDistance(maxi,i);
			if(dis[maxi][i]>maxx)
			{
				maxx=dis[maxi][i];
				maxj=i;
			}
		}
	}
	vector<int>X;
	for(int i=0;i<N;i++)
	{
		if(i!=maxi && i!=maxj)
		{
			dis[maxj][i]=dis[i][maxj]=getDistance(maxj,i);
			X.push_back((dis[maxi][i]-dis[maxj][i]+maxx)/2);
		}
	}
	sort(X.begin(),X.end());
	for(auto &k:X)
	{
		R=min(R,max(maxx-k,k));
	}
	int ch=-1;
	int cnt[3];
	for(int i=0;i<3;i++)cnt[i]=0;
	cnt[0]=cnt[2]=1;
	for(auto &k:X)
	{
		if(k<R)cnt[0]++;
		else if(k==R)cnt[1]++;
		else cnt[2]++;
	}
	if(cnt[0]<=N/2 && cnt[1]<=N/2 && cnt[2]<=N/2)ch=1;
	for(int i=0;i<3;i++)cnt[i]=0;
	cnt[0]=cnt[2]=1;
	for(auto &k:X)
	{
		if(k<maxx-R)cnt[0]++;
		else if(k==maxx-R)cnt[1]++;
		else cnt[2]++;
	}
	if(cnt[0]<=N/2 && cnt[1]<=N/2 && cnt[2]<=N/2)ch=1;
 
 
	return ch*R;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:133:13: warning: declaration of 'X' shadows a global declaration [-Wshadow]
  133 |  vector<int>X;
      |             ^
towns.cpp:26:12: note: shadowed declaration is here
   26 | vector<tri>X;
      |            ^
towns.cpp:147:6: warning: declaration of 'ch' shadows a global declaration [-Wshadow]
  147 |  int ch=-1;
      |      ^~
towns.cpp:21:5: note: shadowed declaration is here
   21 | int ch,n;
      |     ^~

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39