oj.uz

Submission #132793

# Submission time Handle Problem Language Result Execution time Memory
132793 2019-07-19T14:52:48 Z parkky None (KOI17_cat) C++14
0 / 100
 2000 ms 23160 KB 
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int N,M,p[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],endfun,vis[300001],anycyc;
void cycle1(int dep,int del){
	if(vis[his[dep-1]]){
		if(his[dep-1]==his[dep-3])return;
		anycyc=1,endfun=1;
		return;
	}
	vis[his[dep-1]]=dep;
	for(int i=p[his[dep-1]-1];i<p[his[dep-1]];i++){
		if((his[dep]=rd[i].b)==del)continue;
		cycle1(dep+1,del);
		if(endfun)return;
	}
	vis[his[dep-1]]=0;
}
long long solve1(){
	long long R=0;
	for(int i=1;i<=N;i++){
		his[0]=1,endfun=0,anycyc=0;
		memset(vis,0,sizeof(vis));
		cycle1(1,i);
		if(!anycyc)R+=i;
	}
	return R;
}
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:38: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:41: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 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1528 KB Output is correct
5 Correct 899 ms 1836 KB Output is correct
6 Incorrect 734 ms 1784 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 11064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2052 ms 23160 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1528 KB Output is correct
5 Correct 899 ms 1836 KB Output is correct
6 Incorrect 734 ms 1784 KB Output isn't correct
7 Halted 0 ms 0 KB -