oj.uz

Submission #132654

# Submission time Handle Problem Language Result Execution time Memory
132654 2019-07-19T09:39:06 Z parkky None (KOI17_cat) C++14
23 / 100
 2000 ms 10744 KB 
#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;
void cycle(int dep){
	if(endfun)return;
	if(his[dep-1]==his[dep-3])return;
	for(int i=0;i<dep-3;i++){
		if(his[dep-1]==his[i]){
			cycs=i,cyce=dep-1,endfun=1;
			return;
		}
	}
	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;
	}
}
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

cat.cpp: In function 'int main()':
cat.cpp:56: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:59: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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 10120 KB Output is correct
2 Correct 219 ms 8888 KB Output is correct
3 Correct 214 ms 8796 KB Output is correct
4 Correct 205 ms 9028 KB Output is correct
5 Correct 192 ms 8824 KB Output is correct
6 Correct 295 ms 9080 KB Output is correct
7 Correct 212 ms 8996 KB Output is correct
8 Correct 266 ms 8944 KB Output is correct
9 Correct 246 ms 9052 KB Output is correct
10 Correct 293 ms 8924 KB Output is correct
11 Correct 319 ms 9080 KB Output is correct
12 Correct 357 ms 9336 KB Output is correct
13 Correct 278 ms 9080 KB Output is correct
14 Correct 474 ms 9212 KB Output is correct
15 Correct 456 ms 9384 KB Output is correct
16 Execution timed out 2064 ms 10744 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 10104 KB Output is correct
2 Correct 153 ms 8740 KB Output is correct
3 Correct 141 ms 8796 KB Output is correct
4 Correct 186 ms 8796 KB Output is correct
5 Correct 140 ms 8568 KB Output is correct
6 Correct 147 ms 8568 KB Output is correct
7 Correct 171 ms 8568 KB Output is correct
8 Correct 129 ms 8540 KB Output is correct
9 Correct 168 ms 8432 KB Output is correct
10 Correct 142 ms 8304 KB Output is correct
11 Correct 141 ms 8312 KB Output is correct
12 Correct 142 ms 8284 KB Output is correct
13 Correct 143 ms 8236 KB Output is correct
14 Correct 141 ms 8284 KB Output is correct
15 Correct 153 ms 7928 KB Output is correct
16 Correct 149 ms 7892 KB Output is correct
17 Correct 152 ms 8068 KB Output is correct
18 Correct 163 ms 8016 KB Output is correct
19 Correct 158 ms 8056 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -