1 Source Code
2 Problem: 3683 User: theorix
3 Memory: 23864K Time: 188MS
4 Language: C++ Result: Accepted
5
6 * Source Code
7
8 #include<iostream>
9 #include<algorithm>
10 using namespace std;
11 const int NN=1009;
12 int visit[NN*2];
13 int in[NN*2];
14 int n;
15 int order[NN*2],order_t;
16 int belong[NN*2],belong_t;
17 struct seq
18 {
19 int start,end;
20 }v[NN*2];
21 struct node
22 {
23 int id;
24 node *next;
25 }mem[5000000],path[NN*2],rpath[NN*2],way[NN*2],way2[NN*2];
26 int mem_t;
27 inline bool cross(int i,int j)
28 {
29 if(v[i].start>=v[j].end||v[i].end<=v[j].start)return false;
30 return true;
31 }
32 inline void link(int i,int j)
33 {
34 node*t=&mem[mem_t++];
35 t->id=j;
36 t->next=path[i].next;
37 path[i].next=t;
38 t=&mem[mem_t++];
39 t->id=i;
40 t->next=rpath[j].next;
41 rpath[j].next=t;
42 }
43 void dfs(int k)
44 {
45 visit[k]=1;
46 node *t;
47 for(t=path[k].next;t;t=t->next)
48 {
49 if(!visit[t->id])
50 dfs(t->id);
51 }
52 order[++order_t]=k;
53 }
54 void rdfs(int k)
55 {
56 visit[k]=1;
57 belong[k]=belong_t;
58 node *t;
59 for(t=rpath[k].next;t;t=t->next)
60 {
61 if(!visit[t->id])
62 rdfs(t->id);
63 }
64 }
65 bool check()
66 {
67 int i;
68 for(i=1;i<=n;i++)
69 if(belong[i*2-1]==belong[i*2])
70 return false;
71 return true;
72 }
73 void Dfs(int k)
74 {
75 visit[k]=2;
76 node *t;
77 for(t=way[k].next;t;t=t->next)
78 {
79 if(!visit[t->id])
80 {
81 Dfs(t->id);
82 }
83 }
84 }
85 void display()
86 {
87 int i,j;node *t,*tt;
88 memset(in,0,sizeof(in));
89 for(i=1;i<=2*n;i++)
90 {
91 for(t=path[i].next;t;t=t->next)
92 {
93 int a=belong[i],b=belong[t->id];
94 if(a!=b)
95 {
96 for(tt=way[b].next;tt;tt=tt->next)
97 {
98 if(tt->id==a)break;
99 }
100 if(!tt)
101 {
102 tt=&mem[mem_t++];
103 tt->id=a;
104 tt->next=way[b].next;
105 way[b].next=tt;
106 in[a]++;
107 }
108 }
109 }
110 }
111 for(i=1;i<=n;i++)
112 {
113 int a=belong[i*2-1],b=belong[i*2];
114 for(t=way2[b].next;t;t=t->next)
115 if(t->id==a)
116 break;
117 if(!t)
118 {
119 tt=&mem[mem_t++];
120 tt->id=a;
121 tt->next=way2[b].next;
122 way2[b].next=tt;
123 }
124 for(t=way2[a].next;t;t=t->next)
125 if(t->id==b)
126 break;
127 if(!t)
128 {
129 tt=&mem[mem_t++];
130 tt->id=b;
131 tt->next=way2[a].next;
132 way2[a].next=tt;
133 }
134 }
135 memset(visit,0,sizeof(visit));
136 order_t=0;
137 for(i=1;i<=belong_t;i++)
138 if(in[i]==0)
139 order[++order_t]=i,visit[i]=1;
140 int q[NN*2],qt=0;
141 while(order_t>=1)
142 {
143 int tmp=order[order_t--];
144 q[++qt]=tmp;
145 for(t=way[tmp].next;t;t=t->next)
146 if(!visit[t->id])
147 {
148 in[t->id]--;
149 if(in[t->id]==0)
150 order[++order_t]=t->id,visit[t->id]=1;
151 }
152 }
153 memset(visit,0,sizeof(visit));
154 for(i=1;i<=qt;i++)
155 {
156 if(!visit[q[i]])
157 {
158 visit[q[i]]=1;
159 for(t=way2[q[i]].next;t;t=t->next)
160 {
161 if(!visit[t->id])
162 Dfs(t->id);
163 }
164 }
165 }
166 for(i=1;i<=n*2;i++)
167 if(visit[belong[i]]==1)
168 {
169 int start=v[i].start;
170 int end=v[i].end;
171 printf("%02d:%02d %02d:%02d\n",start/60,start%60,end/60,end%60);
172 }
173 }
174 int main()
175 {
176 mem_t=0;
177 scanf("%d",&n);
178 int i,j,k;
179 char ch1[9],ch2[9];
180 int t,tmp;
181 for(i=1;i<=n;i++)
182 {
183 scanf("%s%s%d",&ch1,&ch2,&t);
184 v[2*i-1].start=atoi(ch1)*60+atoi(ch1+3);
185 v[2*i-1].end=v[2*i-1].start+t;
186 v[2*i].end=atoi(ch2)*60+atoi(ch2+3);
187 v[2*i].start=v[2*i].end-t;
188 }
189 for(i=1;i<=n;i++)
190 {
191 for(j=i+1;j<=n;j++)
192 {
193 if(cross(i*2-1,j*2-1))
194 {
195 link(i*2-1,j*2);
196 link(j*2-1,i*2);
197 }
198 if(cross(i*2-1,j*2))
199 {
200 link(i*2-1,j*2-1);
201 link(j*2,i*2);
202 }
203 if(cross(i*2,j*2-1))
204 {
205 link(i*2,j*2);
206 link(j*2-1,i*2-1);
207 }
208 if(cross(i*2,j*2))
209 {
210 link(i*2,j*2-1);
211 link(j*2,i*2-1);
212 }
213 }
214 }
215 memset(visit,0,sizeof(visit));
216 order_t=0;
217 for(i=1;i<=2*n;i++)
218 {
219 if(!visit[i])
220 dfs(i);
221 }
222 memset(visit,0,sizeof(visit));
223 belong_t=0;
224 for(i=order_t;i>=1;i--)
225 {
226 if(!visit[order[i]])
227 {
228 ++belong_t;
229 rdfs(order[i]);
230 }
231 }
232 if(!check())
233 printf("NO\n");
234 else
235 {
236 printf("YES\n");
237 display();
238 }
239 }
240
241