T1 P11474 [COCI 2024/2025 #3] 公交车 / Autobus
愤怒，从红升橙足以说明其恶心，考场上调了半小时才过。
这道题的车能够开 \(24\) 小时，而且他能从前一天开到第二天，由于它只能开 \(24\) 小时，所以说发车时间的时候晚于或等于到达时间，说明他开了一天，由于这个，所以我们要处置惩罚 \(3\) 天的情况。
先把全部的时间段存下来，然后分别加 \(1440\) 和 \(2880\) 分钟，暴力匹配，时间复杂度 \(O(600^2) = O(1)\) （不是）。
[code]//# pragma GCC optimize("Ofast")# include # define fr front# define il inline# define fir first# define sec second# define vec vector# define it iterator# define pb push_back# define lb lower_bound# define ub upper_bound# define all(x) x.begin(), x.end()# define mem(a, b) memset(a, b, sizeof(a))# define lc (t[p].l)# define rc (t[p].r)# define ls(x) (x (i)) & 1)# define set1(x, i) ((x) | (1 > ch; m1 += ch - '0'; cin >> ch >> ch; cin >> h2 >> ch >> ch; m2 = (ch - '0') * 10; cin >> ch; m2 += ch - '0'; int t1 = h1 * 60 + m1; int t2 = h2 * 60 + m2; if(t1 > t2) tmp1.pb({t1, t2 + 1440}); else tmp1.pb({t1, t2}); } else{ cin >> h1 >> ch >> ch; m1 = (ch - '0') * 10; cin >> ch; m1 += ch - '0'; cin >> ch >> ch; cin >> h2 >> ch >> ch; m2 = (ch - '0') * 10; cin >> ch; m2 += ch - '0'; int t1 = h1 * 60 + m1; int t2 = h2 * 60 + m2; if(t1 > t2) tmp2.pb({t1, t2 + 1440}); else tmp2.pb({t1, t2}); } } each2(x, tmp1){ v1.pb(x); v1.pb({x.fir + 1440, x.sec + 1440}); v1.pb({x.fir + 2880, x.sec + 2880}); } each2(x, tmp2){ v2.pb(x); v2.pb({x.fir + 1440, x.sec + 1440}); v2.pb({x.fir + 2880, x.sec + 2880}); } each2(a, v1){ each2(b, v2){ if(a.sec >= b.fir) continue; ans = min(ans, b.sec - a.fir + 1); } } if(ans == INF1) cout x >> y; if(deep[y] == deep[x] - 1){ cout = deep[y] + 1) z = f[z]; s --; } cout |
