Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:怎么一直tle,数据有问题吧

Posted by a1b3c7d9 at 2019-11-07 15:59:47 on Problem 3683
In Reply To:怎么一直tle,数据有问题吧 Posted by:a1b3c7d9 at 2019-11-07 15:59:27
#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#define il inline
#define ri register
#define Size 2050
using namespace std;
struct point{
	point*next;int to;
}*head[Size];
struct inter{int l,r;}s[Size][2];
int dfn[Size],low[Size],sta[Size],
	top,tim,vis[Size],cnt,be[Size],
	a[Size];
void tarjan(int);
il void read(int&),link(int,int),
	print60(int),getime(int&);
int main(){
	//freopen("in","r",stdin);
	//freopen("out","w",stdout);
	int n;read(n);clock_t t1(clock());
	for(int i(1),l,r,d;i<=n;++i){
		getime(l),getime(r),read(d);
		s[i][0]={l,l+d},s[i][1]={r-d,r};
	}for(int i(1),j,k,l;i<=n;++i)
		 for(j=i+1;j<=n;++j)
			 for(k=0;k<2;++k)
				 for(l=0;l<2;++l)
					 if(!(s[i][k].l>=s[j][l].r||s[i][k].r<=s[j][l].l))
						 link(i+k*n,j+(1-l)*n),link(j+l*n,i+(1-k)*n);
	memset(a,-1,sizeof(a));for(int i(1);i<=n<<1;++i)if(!dfn[i])tarjan(i);
	for(int i(1);i<=n;++i)if(be[i]==be[i+n])return puts("NO"),0;puts("YES");
	for(int i(1);i<=n;putchar('\n'),++i)
		if(be[i]<be[i+n])
			print60(s[i][0].l),putchar(' '),print60(s[i][0].r);
		else print60(s[i][1].l),putchar(' '),print60(s[i][1].r);
	return 0;
}
il void getime(int&x){
	int a,b;read(a),read(b),x=a*60+b;
}
il void print60(int x){
	printf("%02d:%02d",x/60,x%60);
}
void tarjan(int x){
	dfn[x]=low[x]=++tim,sta[++top]=x,vis[x]=1;
	for(point*i(head[x]);i!=NULL;i=i->next)
		if(!dfn[i->to])
			tarjan(i->to),low[x]=min(low[x],low[i->to]);
		else if(vis[i->to])low[x]=min(low[x],dfn[i->to]);
	if(dfn[x]==low[x]){++cnt;
		do vis[sta[top]]=0,be[sta[top]]=cnt;
		while(sta[top--]!=x);
	}
}
il void link(int u,int v){
	head[u]=new point{head[u],v};
}
il void read(int&x){
	x^=x;ri char c;while(c=getchar(),c<'0'||c>'9');
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator