// 2-SAT based solution (O(n^2)) // if compiled with -DSLOW, will give O(n^3) version #include #include #include #include #include #include #include using namespace std; int parse( string s ) { string d = s.substr(0,3); assert( s[3]==':' ); string h = s.substr(4,2); int hh = atoi(h.c_str()); assert(0<=hh&&hh<24); assert( s[6]==':' ); string m = s.substr(7,2); int mm = atoi(m.c_str()); assert(0<=mm&&mm<60); return // No reservation is made at SUNDAY ( d=="MON" ? 0 : d=="TUE" ? 1 : d=="WED" ? 2 : d=="THU" ? 3 : d=="FRI" ? 4 : d=="SAT" ? 5 : (assert(false),-1) ) *60*24 + hh*60 + mm; } bool conflict( pair a, pair b ) { return !(a.second <= b.first || b.second <= a.first); } typedef map< int, vector > graph; bool is_there_a_path( graph& G, int src, int dst, set& visited ) { visited.clear(); visited.insert(src); if( G.count(src) ) for(vector q(1,src); !q.empty(); ) { int v = q.back(); q.pop_back(); if( G.count(v) ) for(int i=0; i!=G[v].size(); ++i) if( G[v][i] == dst ) return true; else if( !visited.count(G[v][i]) ) { visited.insert(G[v][i]); q.push_back(G[v][i]); } } return false; } int main() { int T; cin >> T; while(T--) { // Input map< int, pair > cand; typedef map >::iterator CIT; int n; cin >> n; assert( 1<=n && n<=1000 ); for(int i=1; i<=n; ++i) { string r1, r2, r3, r4; cin >> r1 >> r2 >> r3 >> r4; cand[+i] = make_pair( parse(r1), parse(r2) ); cand[-i] = make_pair( parse(r3), parse(r4) ); } // Construt a graph // an edge [+i] -> [-j] means: // if the candidate +i is taken, then (since +i and +j conflicts) // the candidate -j must be taken graph G; for(CIT i=cand.begin(); i!=cand.end(); ++i) for(CIT j=cand.begin(); j!=cand.end(); ++j) if( abs(i->first)!=abs(j->first) && conflict(i->second, j->second) ) G[i->first].push_back( -j->first ); // Solve by 2-SAT like strategy // YES iff there're no paths (+i ->^* -i) && (-i ->^* +i) // - If there're such paths, clearly it's NO. Since we can // take neigher +i nor -i. // - If there're no such paths, we can assign the rooms in the following way: // = Randomly choose "i". wlog assume no path +i ->^* -i exist. // = Assign the room +i // = Assign all rooms reachable from +i (this doesn't cause conflicts, // since there's no path: +i ->^* -i) // = Remove all assigned seminars (both +j and -j) // = Repeat above 4 steps until all rooms are assigned // (this repetation doesn't cause conflicts, too. if it does (if // "all rooms reachable" contains a candidate already decided not // to be assigned), there must be an edge +k -> -a (+k new selection, // -a already removed). But in that case, there must also be an edge // +a -> -k. So +k and -k must be already removed. So it won't happen.) string answer = "YES"; for(int i=1; i<=n; ++i) { set visitables; if( is_there_a_path(G, +i, -i, visitables) && is_there_a_path(G, -i, +i, visitables) ) {answer = "NO"; break;} #ifndef SLOW for(set::iterator it=visitables.begin(); it!=visitables.end(); ++it) G.erase( +*it ), G.erase( -*it ); #endif } cout << answer << endl; } }