Submission #32733232

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = long long;


int main(){
  int n; cin >> n;
  vector<ll> x(n), y(n), p(n);
  for(int i=0; i<n; i++)cin>>x[i]>>y[i]>>p[i];
  ll l=0, r=5e9;
  while(r - l > 1){
    ll m=(r+l)/2;
    bool e[n][n];
    for(int i=0; i<n; i++)for(int j=0; j<n; j++)e[i][j]=0;
    for(int i=0; i<n; i++)for(int j=0; j<n; j++){
      if(abs(x[i]-x[j])+abs(y[i]-y[j])<=p[i]*m)e[i][j]=1;
    }
    
    bool can=false;
    for(int i=0; i<n; i++){
      vector<int> v(n, 0); v[i]=1;
      queue<int> q; q.push(i);
      while(!q.empty()){
        int top=q.front(); q.pop();
        for(int j=0; j<n; j++){
          if(!v[j]&&e[top][j]){
            v[j]=1, q.push(j);
          }
        }
      }
      bool tmp=true;
      for(int j=0; j<n; j++)if(!v[j])tmp=false;
      if(tmp)can=true;
    }
    if(can)r=m;
    else l=m;
  }
  cout<<r<<endl;
}

Submission Info

Submission Time
Task D - Jumping Takahashi 2
User harady
Language C++ (GCC 9.2.1)
Score 400
Code Size 929 Byte
Status AC
Exec Time 745 ms
Memory 3652 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 40
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt
All 00_sample_01.txt, 00_sample_02.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 02_max_01.txt, 02_max_02.txt, 02_max_03.txt, 02_max_04.txt, 02_max_05.txt, 02_max_06.txt, 02_max_07.txt, 02_max_08.txt, 02_max_09.txt, 02_max_10.txt, 02_max_11.txt, 02_max_12.txt, 02_max_13.txt, 02_max_14.txt, 02_max_15.txt, 02_max_16.txt, 02_max_17.txt, 02_max_18.txt, 02_max_19.txt, 02_max_20.txt, 02_max_21.txt, 02_max_22.txt, 02_max_23.txt, 02_max_24.txt, 02_max_25.txt, 03_handmade_01.txt, 03_handmade_02.txt, 03_handmade_03.txt, 03_handmade_04.txt, 03_handmade_05.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 6 ms 3368 KiB
00_sample_02.txt AC 2 ms 3372 KiB
01_random_01.txt AC 3 ms 3432 KiB
01_random_02.txt AC 2 ms 3540 KiB
01_random_03.txt AC 2 ms 3432 KiB
01_random_04.txt AC 14 ms 3376 KiB
01_random_05.txt AC 5 ms 3548 KiB
01_random_06.txt AC 57 ms 3552 KiB
01_random_07.txt AC 218 ms 3520 KiB
01_random_08.txt AC 17 ms 3544 KiB
02_max_01.txt AC 745 ms 3416 KiB
02_max_02.txt AC 699 ms 3416 KiB
02_max_03.txt AC 705 ms 3468 KiB
02_max_04.txt AC 695 ms 3480 KiB
02_max_05.txt AC 670 ms 3588 KiB
02_max_06.txt AC 694 ms 3596 KiB
02_max_07.txt AC 558 ms 3652 KiB
02_max_08.txt AC 517 ms 3536 KiB
02_max_09.txt AC 550 ms 3472 KiB
02_max_10.txt AC 604 ms 3476 KiB
02_max_11.txt AC 593 ms 3584 KiB
02_max_12.txt AC 562 ms 3540 KiB
02_max_13.txt AC 489 ms 3588 KiB
02_max_14.txt AC 578 ms 3472 KiB
02_max_15.txt AC 485 ms 3472 KiB
02_max_16.txt AC 531 ms 3648 KiB
02_max_17.txt AC 469 ms 3476 KiB
02_max_18.txt AC 463 ms 3600 KiB
02_max_19.txt AC 447 ms 3540 KiB
02_max_20.txt AC 448 ms 3588 KiB
02_max_21.txt AC 475 ms 3596 KiB
02_max_22.txt AC 463 ms 3472 KiB
02_max_23.txt AC 458 ms 3476 KiB
02_max_24.txt AC 425 ms 3476 KiB
02_max_25.txt AC 420 ms 3584 KiB
03_handmade_01.txt AC 2 ms 3368 KiB
03_handmade_02.txt AC 386 ms 3576 KiB
03_handmade_03.txt AC 271 ms 3412 KiB
03_handmade_04.txt AC 387 ms 3412 KiB
03_handmade_05.txt AC 385 ms 3596 KiB