|
|
Спасибо, будем знать Edited by author 25.09.2023 01:13 WA5,and never get Accept without High Eps.It isn't a good Problem. the reason is min(ti+(ti*T+99)/100,100500*ti) can overflow. So you are supposed to change long long into unsigned long long,then you'll get AC. It is okay to use an edge if the next cleaning for this edge begins at the exact moment when you have crossed the edge. In other words a road is cleaned during the open interval (s_i, f_i). Try this test: 100000 99999 0 1 2 1000000 2 3 1000000 ... 99999 100000 1000000 Answer: 10049708502000000 Good Luck! Thanks! HINT for solvers: In the test above, you can get an overflow. Change min(⌈(1 + T/100)* ti⌉, 100500*ti) to long long my_ceil(long long tnow, long long f1, long long t) { if(h1+tnow-f1>h2*h1) return h2*t; //return min(ceil(t+(tnow-f1)*t/100.0), h2*t); if(((tnow-f1)*t) % h1==0) return t+((tnow-f1)*t)/h1; else return t+((tnow-f1)*t)/h1 + h3; } //h1=100; h2=100500; h3=1; where tnow=time now, f1=last cleaning time for this rib, s2=start time of next cleaning Edited by author 26.07.2017 14:10 Edited by author 21.05.2017 17:19 |
|
|