Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:怎么一直tle,数据有问题吧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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator