Submission #132663

#	Time	Username	Problem	Language	Result	Execution time	Memory
132663		parkky	산만한 고양이 (KOI17_cat)	C++14	33 / 100	254 ms	25976 KiB

cat

#include<stdio.h>
#include<algorithm>
using namespace std;
int N,M,p[300001],imp[300001];
struct road{
	int a,b;
}rd[600000];
int so(road x,road y){
	return x.a<y.a||(x.a==y.a&&x.b<y.b);
}
int his[300001],cycs,cyce,endfun,vis[300001];
void cycle(int dep){
	if(vis[his[dep-1]]){
		if(his[dep-1]==his[dep-3])return;
		cycs=vis[his[dep-1]]-1,cyce=dep-1,endfun=1;
		return;
	}
	vis[his[dep-1]]=dep;
	for(int i=p[his[dep-1]-1];i<p[his[dep-1]];i++){
		his[dep]=rd[i].b;
		cycle(dep+1);
		if(endfun)return;
	}
	vis[his[dep-1]]=0;
}
long long solve2(){
	long long R=0;
	his[0]=1;
	cycle(1);
	for(int i=cycs;i<cyce;i++){
		R+=his[i];
	}
	return R;
}
int near(int x,int y){
	return x-y==1||y-x==1||x-y==N-1||y-x==N-1;
}
long long solve3(){
	int list[2]={};
	for(int i=0;i<2*M;i++){
		if(rd[i].a>rd[i].b)continue;
		if(!near(rd[i].a,rd[i].b)){
			if(list[0]==0)list[0]=rd[i].a,list[1]=rd[i].b;
			else if(list[0]==rd[i].a||list[0]==rd[i].b)list[1]=-1;
			else if(list[1]==rd[i].a||list[1]==rd[i].b)list[0]=list[1],list[1]=-1;
			else list[0]=-1;
		}
	}
	if(list[0]==-1)return 0;
	if(list[1]==-1)return list[0];
	if(list[0])return list[0]+list[1];
	return N*(N+1)/2;
}
int main(){
	scanf("%d%d",&N,&M);
	for(int i=0;i<M;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		rd[2*i]={x,y};
		rd[2*i+1]={y,x};
	}
	sort(rd,rd+2*M,so);
	for(int i=0,j=0;i<2*M;i++){
		if(rd[i].a>j)p[j++]=i;
	}
	p[N]=2*M;
	printf("%lld",N==M?solve2():solve3());
	return 0;
}

Compilation message (stderr)

cat.cpp: In function 'int main()':
cat.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&N,&M);
  ~~~~~^~~~~~~~~~~~~~
cat.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 55