1307.md (10994B)
1 Source: https://codeforces.com/blog/entry/73953 2 3 [1307A - Cow and Haybales](/contest/1307/problem/A) 4 5 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <iostream> 15 using namespace std; 16 17 int N,D,a[105]; 18 19 int main(){ 20 int T; cin>>T; 21 while (T--){ 22 cin>>N>>D; 23 for (int i=1;i<=N;i++) 24 cin>>a[i]; 25 while (D--){ //loop over D days 26 for (int i=2;i<=N;i++) 27 if (a[i]>0){ //move closest haybale over 28 a[i]--; 29 a[i-1]++; 30 break; 31 } 32 } 33 cout<<a[1]<<endl; 34 } 35 } 36 ``` 37 38 **Alternative O(n) Solution:** 39 40 ``` 41 #include <iostream> 42 using namespace std; 43 44 int N,D,a[105],ans; 45 46 int main(){ 47 int T; cin>>T; 48 while (T--){ 49 cin>>N>>D; 50 for (int i=1;i<=N;i++) 51 cin>>a[i]; 52 for (int i=2;i<=N;i++){ 53 int move=min(a[i],D/(i-1)); //number of haybales we can move from pile i to pile 1 54 a[1]+=move; //update pile 1 55 D-=move*(i-1); //update remaining days 56 } 57 cout<<a[1]<<endl; 58 } 59 } 60 ``` 61 62 [1307B - Cow and Friend](/contest/1307/problem/B) 63 64 Idea: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining") 65 66 **Tutorial** 67 68 Tutorial is loading... 69 70 **Solution** 71 72 ``` 73 #include <iostream> 74 #include <set> 75 #include <algorithm> 76 using namespace std; 77 78 set<int>a; 79 //you don't have to use set, it was just easier for us 80 81 int main(){ 82 int T; cin>>T; 83 while (T--){ 84 int N,X; 85 cin>>N>>X; 86 int far=0; //largest favorite number 87 for (int i=0;i<N;i++){ 88 int A; 89 cin>>A; 90 a.insert(A); 91 far=max(far,A); 92 } 93 if (a.count(X)) //X is favorite number 94 cout<<1<<endl; 95 else 96 cout<<max(2,(X+far-1)/far)<<endl; //expression as explained in tutorial 97 a.clear(); 98 } 99 } 100 ``` 101 102 [1307C - Cow and Message](/contest/1307/problem/C) 103 104 Idea: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining") 105 106 **Tutorial** 107 108 Tutorial is loading... 109 110 **Solution** 111 112 ``` 113 #include <iostream> 114 using namespace std; 115 116 typedef long long ll; 117 ll arr1[26],arr2[26][26]; 118 119 int main(){ 120 string S; 121 cin>>S; 122 for (int i=0;i<S.length();i++){ 123 int c=S[i]-'a'; 124 for (int j=0;j<26;j++) 125 arr2[j][c]+=arr1[j]; 126 arr1[c]++; 127 } 128 ll ans=0; 129 for (int i=0;i<26;i++) 130 ans=max(ans,arr1[i]); 131 for (int i=0;i<26;i++) 132 for (int j=0;j<26;j++) 133 ans=max(ans,arr2[i][j]); 134 cout<<ans<<endl; 135 } 136 ``` 137 138 [1307D - Cow and Fields](/contest/1307/problem/D) 139 140 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix") 141 142 **Tutorial** 143 144 Tutorial is loading... 145 146 **Solution** 147 148 ``` 149 #include <cstdio> 150 #include <vector> 151 #include <algorithm> 152 153 const int INF=1e9+7; 154 155 int N; 156 int as[200005]; 157 158 std::vector<int> edges[200005]; 159 160 int dist[2][200005]; 161 int q[200005]; 162 163 void bfs(int* dist,int s){ 164 std::fill(dist,dist+N,INF); 165 int qh=0,qt=0; 166 q[qh++]=s; 167 dist[s]=0; 168 while(qt<qh){ 169 int x=q[qt++]; 170 for(int y:edges[x]){ 171 if(dist[y]==INF){ 172 dist[y]=dist[x]+1; 173 q[qh++]=y; 174 } 175 } 176 } 177 } 178 179 int main(){ 180 int M,K; 181 scanf("%d %d %d",&N,&M,&K); 182 for(int i=0;i<K;i++){ 183 scanf("%d",&as[i]); 184 as[i]--; 185 } 186 std::sort(as,as+K); 187 for(int i=0;i<M;i++){ 188 int X,Y; 189 scanf("%d %d",&X,&Y); 190 X--,Y--; 191 edges[X].push_back(Y); 192 edges[Y].push_back(X); 193 } 194 bfs(dist[0],0); 195 bfs(dist[1],N-1); 196 std::vector<std::pair<int,int> > data; 197 for(int i=0;i<K;i++){ 198 data.emplace_back(dist[0][as[i]]-dist[1][as[i]],as[i]); 199 } 200 std::sort(data.begin(),data.end()); 201 int best=0; 202 int max=-INF; 203 for(auto it:data){ 204 int a=it.second; 205 best=std::max(best,max+dist[1][a]); 206 max=std::max(max,dist[0][a]); 207 } 208 printf("%d\n",std::min(dist[0][N-1],best+1)); 209 } 210 ``` 211 212 [1307E - Cow and Treats](/contest/1307/problem/E) 213 214 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix") 215 216 **Tutorial** 217 218 Tutorial is loading... 219 220 **Solution** 221 222 ``` 223 #include <cstdio> 224 #include <vector> 225 #include <algorithm> 226 #include <cassert> 227 228 const int MOD=1e9+7; 229 230 int modexp(int base,int exp){ 231 int ac=1; 232 for(;exp;exp>>=1){ 233 if(exp&1) ac=1LL*ac*base%MOD; 234 base=1LL*base*base%MOD; 235 } 236 return ac; 237 } 238 239 int inverse(int x){ 240 return modexp(x,MOD-2); 241 } 242 243 int fs[100005]; 244 int left[100005],right[100005]; 245 std::vector<int> cows[100005];//cows[f]: hunger of cows that like flavor f 246 int asleep[100005]; 247 int ways[100005]; 248 int total_asleep=0,total_ways=1; 249 250 void calc_ways(int f){ 251 int a=std::upper_bound(cows[f].begin(),cows[f].end(),left[f])-cows[f].begin(); 252 int b=std::upper_bound(cows[f].begin(),cows[f].end(),right[f])-cows[f].begin(); 253 if(a>b) std::swap(a,b); 254 long long cnt2=1LL*a*b-a; 255 int cnt1=a+b; 256 cnt2%=MOD; 257 if(cnt2>0){ 258 asleep[f]=2; 259 ways[f]=cnt2; 260 }else if(cnt1>0){ 261 asleep[f]=1; 262 ways[f]=cnt1; 263 }else{ 264 asleep[f]=0; 265 ways[f]=1; 266 } 267 } 268 269 //fixed left cow, with hunger left[i] 270 //precondition: such cow exists 271 void calc_ways_stuck(int f){ 272 int b=std::upper_bound(cows[f].begin(),cows[f].end(),right[f])-cows[f].begin(); 273 if(right[f]>=left[f]) 274 b--; 275 int cnt2=b; 276 if(cnt2>0){ 277 asleep[f]=2; 278 ways[f]=cnt2; 279 }else{ 280 asleep[f]=1; 281 ways[f]=1; 282 } 283 } 284 285 int ans_asleep=0,ans_ways=0; 286 287 void add_to_ans(int asleep,int ways){ 288 if(asleep>ans_asleep){ 289 ans_asleep=asleep; 290 ans_ways=0; 291 } 292 if(asleep==ans_asleep) 293 ans_ways=(ans_ways+ways)%MOD; 294 } 295 296 int main(){ 297 int N,M; 298 scanf("%d %d",&N,&M); 299 for(int i=1;i<=N;i++){ 300 scanf("%d",&fs[i]); 301 right[fs[i]]++; 302 } 303 for(int i=0;i<M;i++){ 304 int F,H; 305 scanf("%d %d",&F,&H); 306 cows[F].push_back(H); 307 } 308 for(int f=1;f<=N;f++) 309 std::sort(cows[f].begin(),cows[f].end()); 310 for(int f=1;f<=N;f++){ 311 calc_ways(f); 312 total_asleep+=asleep[f]; 313 total_ways=1LL*total_ways*ways[f]%MOD; 314 } 315 add_to_ans(total_asleep,total_ways); 316 for(int i=1;i<=N;i++){ 317 total_asleep-=asleep[fs[i]]; 318 total_ways=1LL*total_ways*inverse(ways[fs[i]])%MOD; 319 right[fs[i]]--; 320 left[fs[i]]++; 321 if(std::binary_search(cows[fs[i]].begin(),cows[fs[i]].end(),left[fs[i]])){ 322 calc_ways_stuck(fs[i]); 323 int here_asleep=total_asleep+asleep[fs[i]]; 324 int here_ways=1LL*total_ways*ways[fs[i]]%MOD; 325 add_to_ans(here_asleep,here_ways); 326 } 327 calc_ways(fs[i]); 328 total_asleep+=asleep[fs[i]]; 329 total_ways=1LL*total_ways*ways[fs[i]]%MOD; 330 } 331 printf("%d %d\n",ans_asleep,ans_ways); 332 } 333 ``` 334 335 [1307F - Cow and Vacation](/contest/1307/problem/F) 336 337 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix") 338 339 **Tutorial** 340 341 Tutorial is loading... 342 343 **Solution** 344 345 ``` 346 #include <cstdio> 347 #include <vector> 348 #include <cassert> 349 #include <queue> 350 #include <algorithm> 351 352 const int INF=1e9+7; 353 354 std::vector<int> edges[400005]; 355 356 int anc[19][400005]; 357 int depth[400005]; 358 359 void dfs(int node){ 360 for(int child:edges[node]){ 361 edges[child].erase(std::find(edges[child].begin(),edges[child].end(),node)); 362 anc[0][child]=node; 363 for(int k=1;k<19;k++){ 364 anc[k][child]=anc[k-1][anc[k-1][child]]; 365 } 366 depth[child]=depth[node]+1; 367 dfs(child); 368 } 369 } 370 371 int la(int node,int len){ 372 for(int k=19-1;k>=0;k--){ 373 if(len&(1<<k)){ 374 node=anc[k][node]; 375 } 376 } 377 return node; 378 } 379 380 int lca(int a,int b){ 381 if(depth[a]<depth[b]) std::swap(a,b); 382 a=la(a,depth[a]-depth[b]); 383 if(a==b) return a; 384 for(int k=19-1;k>=0;k--){ 385 if(anc[k][a]!=anc[k][b]){ 386 a=anc[k][a]; 387 b=anc[k][b]; 388 } 389 } 390 return anc[0][a]; 391 } 392 393 //move x steps from a to b 394 //assumes x<=dist(a,b) 395 int walk(int a,int b,int x){ 396 int c=lca(a,b); 397 if(x<=depth[a]-depth[c]){ 398 return la(a,x); 399 } 400 int excess=x-(depth[a]-depth[c]); 401 assert(excess<=(depth[b]-depth[c])); 402 return la(b,depth[b]-depth[c]-excess); 403 } 404 405 int uf[400005]; 406 int dist[400005];//dist[x]=0 iff x is rest stop 407 408 int find(int a){ 409 while(a!=uf[a]){ 410 a=uf[a]=uf[uf[a]]; 411 } 412 return a; 413 } 414 415 bool query(int K){ 416 int A,B; 417 scanf("%d %d",&A,&B); 418 A--,B--; 419 int C=lca(A,B); 420 if(depth[A]+depth[B]-2*depth[C]<=2*K){ 421 return true; 422 }else{ 423 return find(walk(A,B,K))==find(walk(B,A,K)); 424 } 425 } 426 427 int main(){ 428 int N,K,R; 429 scanf("%d %d %d",&N,&K,&R); 430 int oldN=N; 431 for(int i=0;i<oldN-1;i++){ 432 int X,Y; 433 scanf("%d %d",&X,&Y); 434 X--,Y--; 435 edges[X].push_back(N); 436 edges[N].push_back(X); 437 edges[Y].push_back(N); 438 edges[N].push_back(Y); 439 N++; 440 } 441 for(int i=0;i<N;i++){ 442 uf[i]=i; 443 } 444 std::fill(dist,dist+N,INF); 445 std::queue<int> frontier; 446 for(int i=0;i<R;i++){ 447 int X; 448 scanf("%d",&X); 449 X--; 450 dist[X]=0; 451 frontier.push(X); 452 } 453 while(!frontier.empty()){ 454 int x=frontier.front(); 455 if(dist[x]>K-1) break; 456 frontier.pop(); 457 for(int y:edges[x]){ 458 uf[find(y)]=find(x); 459 if(dist[y]==INF){ 460 dist[y]=dist[x]+1; 461 frontier.push(y); 462 } 463 } 464 } 465 dfs(0); 466 int V; 467 scanf("%d",&V); 468 while(V--){ 469 if(query(K)){ 470 printf("YES\n"); 471 }else{ 472 printf("NO\n"); 473 } 474 } 475 } 476 ``` 477 478 [1307G - Cow and Exercise](/contest/1307/problem/G) 479 480 Idea: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining") 481 482 **Tutorial** 483 484 Tutorial is loading... 485 486 **Solution** 487 488 ``` 489 #include <cstdio> 490 #include <queue> 491 #include <vector> 492 #include <stdint.h> 493 #include <algorithm> 494 495 const long long INF=1e9+7; 496 497 const long long MAXV=50; 498 const long long MAXE=MAXV*(MAXV-1); 499 500 long long SRC,SNK; 501 502 long long elist[MAXE*2]; 503 long long next[MAXE*2]; 504 long long head[MAXV]; 505 long long cap[MAXE*2]; 506 long long cost[MAXE*2]; 507 long long tot=0; 508 509 void add(long long x,long long c,long long w){ 510 elist[tot]=x; 511 cap[tot]=c; 512 cost[tot]=w; 513 next[tot]=head[x]; 514 head[x]=tot++; 515 } 516 517 long long dist[MAXV]; 518 long long prev[MAXV]; 519 std::queue<long long> q; 520 521 long long total_cost=0; 522 long long total_flow=0; 523 524 int main(){ 525 long long N,M; 526 scanf("%lld %lld",&N,&M); 527 SRC=0,SNK=N-1; 528 std::fill(head,head+N,-1); 529 for(long long i=0;i<M;i++){ 530 long long A,B,C; 531 scanf("%lld %lld %lld",&A,&B,&C); 532 A--,B--; 533 add(A,1,C); 534 add(B,0,-C); 535 } 536 std::vector<std::pair<long long,long long> > crit; 537 crit.push_back({0,0}); 538 while(true){ 539 std::fill(dist,dist+N,INF); 540 dist[SRC]=0; 541 prev[SRC]=-1; 542 q.push(SRC); 543 while(!q.empty()){ 544 long long node=q.front(); 545 q.pop(); 546 for(long long e=head[node];e!=-1;e=next[e]){ 547 long long i=elist[e^1]; 548 if(cap[e]){ 549 if(dist[i]>dist[node]+cost[e]){ 550 dist[i]=dist[node]+cost[e]; 551 prev[i]=e; 552 q.push(i); 553 } 554 } 555 } 556 } 557 crit.push_back({1LL*total_flow*dist[SNK]-total_cost,dist[SNK]}); 558 if(dist[SNK]==INF) break; 559 long long aug=INF; 560 for(long long x=SNK;x!=SRC;x=elist[prev[x]]){ 561 aug=std::min(aug,cap[prev[x]]); 562 } 563 for(long long x=SNK;x!=SRC;x=elist[prev[x]]){ 564 cap[prev[x]]-=aug; 565 cap[prev[x]^1]+=aug; 566 } 567 total_flow+=aug; 568 total_cost+=1LL*dist[SNK]*aug; 569 } 570 long long Q; 571 scanf("%lld",&Q); 572 while(Q--){ 573 long long X; 574 scanf("%lld",&X); 575 auto it=std::lower_bound(crit.begin(),crit.end(),std::pair<long long,long long>{X+1,0}); 576 double D=(long double)((X-(it-1)->first)*it->second+(it->first-X)*((it-1)->second))/(it->first-(it-1)->first); 577 printf("%.10lf\n",D); 578 } 579 return 0; 580 } 581 ```