oj.uz

Submission #132764

# Submission time Handle Problem Language Result Execution time Memory
132764 2019-07-19T13:48:21 Z parkky None (KOI17_cat) C++14
10 / 100
 2000 ms 27744 KB 
#include<stdio.h>
#include<algorithm>
#include<string.h>
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],hic[300001],noc;
void cycle1(int dep){
	if(vis[his[dep-1]]){
		if(his[dep-1]==his[dep-3])return;
		cycs=vis[his[dep-1]]-1,cyce=dep-1;
		for(int i=cycs;i<cyce;i++)hic[his[i]]++;
		noc++;
		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;
		cycle1(dep+1);
	}
	vis[his[dep-1]]=0;
}
long long solve1(){
	long long R=0;
	his[0]=1;
	cycle1(1);
	for(int i=1;i<=N;i++)if(hic[i]==noc)R+=i;
	return R;
}
void cycle2(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;
		cycle2(dep+1);
		if(endfun)return;
	}
	vis[his[dep-1]]=0;
}
long long solve2(){
	long long R=0;
	his[0]=1;
	cycle2(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",solve1());
	return 0;
}

Compilation message

cat.cpp: In function 'int main()':
cat.cpp:78: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:81: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 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 5 ms 760 KB Output is correct
12 Correct 5 ms 760 KB Output is correct
13 Correct 6 ms 632 KB Output is correct
14 Correct 6 ms 632 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Execution timed out 2039 ms 632 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 10788 KB Output is correct
2 Correct 247 ms 11480 KB Output is correct
3 Correct 249 ms 11560 KB Output is correct
4 Correct 240 ms 11484 KB Output is correct
5 Correct 242 ms 11380 KB Output is correct
6 Correct 242 ms 12280 KB Output is correct
7 Correct 239 ms 12256 KB Output is correct
8 Correct 258 ms 12260 KB Output is correct
9 Correct 223 ms 11900 KB Output is correct
10 Correct 252 ms 12396 KB Output is correct
11 Correct 242 ms 12664 KB Output is correct
12 Correct 238 ms 12792 KB Output is correct
13 Correct 223 ms 12208 KB Output is correct
14 Correct 232 ms 12012 KB Output is correct
15 Correct 242 ms 12792 KB Output is correct
16 Correct 256 ms 15864 KB Output is correct
17 Correct 269 ms 15988 KB Output is correct
18 Correct 230 ms 14584 KB Output is correct
19 Correct 258 ms 15784 KB Output is correct
20 Correct 253 ms 14712 KB Output is correct
21 Correct 255 ms 13560 KB Output is correct
22 Correct 250 ms 19348 KB Output is correct
23 Correct 245 ms 21240 KB Output is correct
24 Correct 259 ms 13812 KB Output is correct
25 Correct 269 ms 20600 KB Output is correct
26 Correct 150 ms 27128 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 27000 KB Output is correct
2 Correct 181 ms 27716 KB Output is correct
3 Correct 190 ms 27624 KB Output is correct
4 Correct 225 ms 27620 KB Output is correct
5 Correct 207 ms 27640 KB Output is correct
6 Correct 203 ms 27640 KB Output is correct
7 Correct 232 ms 27620 KB Output is correct
8 Correct 184 ms 27744 KB Output is correct
9 Correct 237 ms 27640 KB Output is correct
10 Execution timed out 2025 ms 16484 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 5 ms 760 KB Output is correct
12 Correct 5 ms 760 KB Output is correct
13 Correct 6 ms 632 KB Output is correct
14 Correct 6 ms 632 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Execution timed out 2039 ms 632 KB Time limit exceeded
21 Halted 0 ms 0 KB -