oj.uz

Submission #132663

# Submission time Handle Problem Language Result Execution time Memory
132663 2019-07-19T09:58:33 Z parkky None (KOI17_cat) C++14
33 / 100
 254 ms 25976 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,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

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.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 7928 KB Output is correct
2 Correct 205 ms 8696 KB Output is correct
3 Correct 206 ms 8700 KB Output is correct
4 Correct 199 ms 8672 KB Output is correct
5 Correct 198 ms 8812 KB Output is correct
6 Correct 202 ms 8696 KB Output is correct
7 Correct 190 ms 8664 KB Output is correct
8 Correct 207 ms 8616 KB Output is correct
9 Correct 195 ms 8696 KB Output is correct
10 Correct 202 ms 8716 KB Output is correct
11 Correct 194 ms 8700 KB Output is correct
12 Correct 192 ms 8952 KB Output is correct
13 Correct 193 ms 8856 KB Output is correct
14 Correct 194 ms 9112 KB Output is correct
15 Correct 195 ms 8952 KB Output is correct
16 Correct 208 ms 10636 KB Output is correct
17 Correct 226 ms 14840 KB Output is correct
18 Correct 192 ms 12536 KB Output is correct
19 Correct 246 ms 14072 KB Output is correct
20 Correct 197 ms 12664 KB Output is correct
21 Correct 221 ms 11704 KB Output is correct
22 Correct 254 ms 16332 KB Output is correct
23 Correct 235 ms 19960 KB Output is correct
24 Correct 194 ms 11612 KB Output is correct
25 Correct 221 ms 15404 KB Output is correct
26 Correct 156 ms 25976 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 6904 KB Output is correct
2 Correct 150 ms 7416 KB Output is correct
3 Correct 181 ms 7416 KB Output is correct
4 Correct 196 ms 7368 KB Output is correct
5 Correct 143 ms 7416 KB Output is correct
6 Correct 153 ms 7288 KB Output is correct
7 Correct 185 ms 7348 KB Output is correct
8 Correct 137 ms 7476 KB Output is correct
9 Correct 183 ms 7240 KB Output is correct
10 Correct 142 ms 7160 KB Output is correct
11 Correct 142 ms 7184 KB Output is correct
12 Correct 147 ms 7148 KB Output is correct
13 Correct 146 ms 7288 KB Output is correct
14 Correct 143 ms 7032 KB Output is correct
15 Correct 160 ms 6952 KB Output is correct
16 Correct 148 ms 7024 KB Output is correct
17 Correct 150 ms 6904 KB Output is correct
18 Correct 151 ms 6904 KB Output is correct
19 Correct 156 ms 6844 KB Output is correct

Subtask #4
0 / 55.0

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