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