C++14(g++5.4) 解法, 执行用时: 47ms, 内存消耗: 12196K, 提交时间: 2019-09-21 14:22:51

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e3+10;
const int M=2e7+10;

int head[N],ver[2*M],nex[2*M],tot=1;
inline void add(int x,int y) {
    ver[++tot]=y,nex[tot]=head[x],head[x]=tot;
}

int dfn[N],low[N],num,stk[N],top,ins[N],c[N],cnt;
void tarjan(int x) {
    dfn[x]=low[x]=++num;
    stk[++top]=x;
    ins[x]=1;
    for(int i=head[x]; i; i=nex[i]) {
        int y=ver[i];
        if(!dfn[y]) {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        } else if(ins[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]) {
        ++cnt;
        do {
            ins[stk[top]]=0;
            c[stk[top]]=cnt;
        } while(stk[top--]!=x);
    }
}
int n;
int st[N],ed[N];

inline bool judge(int a,int b,int c,int d) {
    return !(b<=c||d<=a);
}
inline int opp(int x) {
    return x>n?x-n:x+n;
}

int val[N];
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) {
        int a,b,c,d,e;
        scanf("%d:%d%d:%d%d",&a,&b,&c,&d,&e);
        st[i]=a*60+b;
        ed[i]=st[i]+e;
        ed[i+n]=c*60+d;
        st[i+n]=ed[i+n]-e;
        if(e>ed[i+n]-st[i])
        {
            puts("NO");
            return 0;
        }
    }
    for(int i=1; i<=2*n; ++i)
        for(int j=i+1; j<=2*n; ++j) {
            if(i+n!=j)
                if(judge(st[i],ed[i],st[j],ed[j])) {
                    add(i,opp(j));
                    add(j,opp(i));
                }
        }
    for(int i=1; i<=2*n; ++i)
        if(!dfn[i])
            tarjan(i);
    for(int i=1; i<=n; ++i)
        if(c[i]==c[i+n]) {
            puts("NO");
            return 0;
        }
    puts("YES");
    for(int i=1; i<=2*n; ++i)
        val[i]=c[i]>c[opp(i)];

    for(int i=1; i<=n; ++i)
        printf("%02d:%02d %02d:%02d\n",st[i+val[i]*n]/60,st[i+val[i]*n]%60,ed[i+val[i]*n]/60,ed[i+val[i]*n]%60);
    return 0;
}

C++ 解法, 执行用时: 45ms, 内存消耗: 12336K, 提交时间: 2022-04-10 21:04:34

#include<bits/stdc++.h>
using namespace std;
int gi()
{
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 2e3+5;
int n,s[N],t[N],d[N],to[N*N],nxt[N*N],head[N],cnt;
int dfn[N],low[N],tim,Stack[N],top,vis[N],bel[N],scc;
int GetTime(){
	return gi()*60+gi();
}
void OutputTime(int x,char ch)
{
	printf("%.2d:%.2d%c",x/60,x%60,ch);
}
bool Cross(int l1,int r1,int l2,int r2)
{
	if (l1>l2) swap(l1,l2),swap(r1,r2);
	return l2<r1;
}
void link(int u,int v)
{
	to[++cnt]=v;nxt[cnt]=head[u];
	head[u]=cnt;
}
void Tarjan(int u)
{
	dfn[u]=low[u]=++tim;
	Stack[++top]=u;vis[u]=1;
	for (int e=head[u];e;e=nxt[e])
		if (!dfn[to[e]]) Tarjan(to[e]),low[u]=min(low[u],low[to[e]]);
		else if (vis[to[e]]) low[u]=min(low[u],dfn[to[e]]);
	if (dfn[u]==low[u])
	{
		++scc;int v;
		do{
			v=Stack[top--];
			vis[v]=0;bel[v]=scc;
		}while (u!=v);
	}
}
int main(){
	n=gi();
	for (int i=1;i<=n;++i) s[i]=GetTime(),t[i]=GetTime(),d[i]=gi();
	for (int i=1;i<=n;++i)for (int j=i+1;j<=n;++j){
			if (Cross(s[i],s[i]+d[i],s[j],s[j]+d[j]))link(i,j+n),link(j,i+n);
			if (Cross(s[i],s[i]+d[i],t[j]-d[j],t[j]))link(i,j),link(j+n,i+n);
			if (Cross(t[i]-d[i],t[i],s[j],s[j]+d[j]))link(i+n,j+n),link(j,i);
			if (Cross(t[i]-d[i],t[i],t[j]-d[j],t[j]))link(i+n,j),link(j+n,i);
		}
	for (int i=1;i<=2*n;++i) if (!dfn[i]) Tarjan(i);
	for (int i=1;i<=n;++i) if (bel[i]==bel[i+n]) return puts("NO"),0;
	puts("YES");
	for (int i=1;i<=n;++i)
		if (bel[i]<bel[i+n])OutputTime(s[i],' '),OutputTime(s[i]+d[i],'\n');
		else OutputTime(t[i]-d[i],' '),OutputTime(t[i],'\n');
	return 0;
}