oj.uz

Submission #1028357

# Submission time Handle Problem Language Result Execution time Memory
1028357 2024-07-19T17:21:05 Z huutuan Towns (IOI15_towns) C++14
0 / 100
 10 ms 1268 KB 
#include "towns.h"

#include <bits/stdc++.h>

using namespace std;

int dd[200][200];

mt19937 rng(69420);

int GetDistance(int u, int v){
   if (u==v) return 0;
   if (dd[u][v]) return dd[u][v];
   int tmp=getDistance(u, v);
   dd[u][v]=tmp; dd[v][u]=tmp;
   return tmp;
}

int hubDistance(int N, int sub) {
   memset(dd, 0, sizeof dd);
   int u=0, dis=0;
   for (int i=1; i<N; ++i){
      int d=GetDistance(0, i);
      if (d>dis){
         dis=d;
         u=i;
      }
   }
   dis=0;
   int v=u;
   for (int i=0; i<N; ++i) if (i!=u){
      int d=GetDistance(u, i);
      if (d>dis){
         dis=d;
         v=i;
      }
   }
   int len=GetDistance(u, v);
   int ans=1e9;
   vector<pair<int, int>> vv;
   for (int i=0; i<N; ++i) if (i!=u && i!=v){
      int dl=(GetDistance(u, i)+GetDistance(u, 0)-GetDistance(0, i))/2, dr=len-dl;
      ans=min(ans, max(dl, dr));
      vv.emplace_back(dl, dr);
   }
   if (sub<=2) return ans;
   sort(vv.begin(), vv.end());
   vv.resize(unique(vv.begin(), vv.end())-vv.begin());
   int cnt=0;
   for (auto &ii:vv) if (max(ii.first, ii.second)==ans) ++cnt;
   int mx=N/2;
   for (auto &ii:vv) if (max(ii.first, ii.second)==ans){
      int szl=0, szr=0;
      vector<int> child(N);
      iota(child.begin(), child.end(), 0);
      vector<int> is_valid(N);
      auto check=[&](int x, int y) -> bool {
         if (!is_valid[x] || !is_valid[y]) return false;
         return GetDistance(u, x)+GetDistance(u, y)-ii.first*2-GetDistance(x, y)>0;
      };
      for (int i=0; i<N; ++i){
         int dl=(GetDistance(u, i)+GetDistance(u, 0)-GetDistance(0, i))/2;
         if (dl<ii.first) ++szl;
         else if (dl>ii.first) ++szr;
         else is_valid[i]=1;
      }
      if (szl>mx || szr>mx) continue;
      vector<int> v1, v2;
      for (int i:child){
         if (v1.size() && check(v1.back(), i)){
            v2.push_back(i);
         }else{
            v1.push_back(i);
            if (v2.size()) v1.push_back(v2.back()), v2.pop_back();
         }
      }
      bool ff=0;
      if (v1.size()){
         int t=v1.back(); v1.pop_back();
         while (v1.size()){
            if (check(v1.back(), t)){
               if ((int)v1.size()==1) v2.push_back(v1.back()), v1.pop_back();
               else v1.pop_back(), v1.pop_back();
            }else{
               if (v2.empty()){
                  ff=1;
                  break;
               }
               v2.pop_back();
               v1.pop_back();
            }
         }
      }else ff=1;
      if (v2.size()) ff=1;
      if (ff) return ans;
   }
   return -ans;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1116 KB Output is correct
2 Incorrect 7 ms 1104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1116 KB Output is correct
2 Incorrect 9 ms 860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -