oj.uz

Submission #1111854

# Submission time Handle Problem Language Result Execution time Memory
1111854 2024-11-13T07:25:51 Z vjudge1 Shymbulak (IZhO14_shymbulak) C++17
0 / 100
 69 ms 10144 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld double

const int INF = 1e18;
const int sz = 2e5 + 9;

int n1 = -1 , n2 = -1 , cnt1 = 0 , cnt2 = 0;
vector < int > q1;
vector < int > q2;
int n;
vector < vector < int > > adj;
vector < int > dist(sz , -1);
queue < int > q;

void bfs(int s)
{
   dist[s] = 0;
   q.push(s);
   while(!q.empty())
   {
      int v = q.front();
      q.pop();
      for(int u : adj[v])
      {
         if(dist[u] == -1)
         {
            dist[u] = dist[v] + 1;
            q.push(u);
         }
      }
   }
}

void fix()
{
   dist.assign(sz , -1);
   q = {};
}

signed main()
{
   std::ifstream input("shymbulak.in");
   std::ofstream output("shymbulak.out");
   cin >> n;
   adj.resize(n + 1);
   for(int i = 1;i <= n;i++){
      int u , v;
      cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
   }
   bfs(1);
   int maks1 = -1 * INF;
   for(int i = 2;i <= n;i++) maks1 = max(maks1 , dist[i]);
   for(int i = 2;i <= n;i++)
   {
      if(dist[i] == maks1){
         n1 = i;
         break;
      }
   }
   fix();
   int maks = -1 * INF;
   bfs(n1);
   maks1 = -1 * INF;
   for(int i = 1;i <= n;i++)
   {
      if(i == n1) continue;
      maks1 = max(maks1 , dist[i]);
      maks = max(maks , dist[i]);
   }
   for(int i = 1;i <= n;i++)
   {
      if(i == n1) continue;
      if(dist[i] == maks1){
         q1.push_back(i);
         n2 = i;
         cnt1++;
      }
   }
   fix();
   bfs(n2);
   maks1 = -1 * INF;
   for(int i = 1;i <= n;i++)
   {
      if(i == n2) continue;
      maks1 = max(maks1 , dist[i]);
   }
   for(int i = 1;i <= n;i++)
   {
      if(i == n2) continue;
      if(dist[i] == maks1){
         cnt2++;
         q2.push_back(i);
      }
   }
   vector < int > ls;
   int node = -1;
   if(cnt1 > cnt2){
      node = n1;
      ls = q1;
   }
   else{
      node = n2;
      ls = q2;
   }
   cout << max((maks1-1) * 2 , (maks-1) * 2) << endl;
}

Compilation message

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:101:8: warning: variable 'node' set but not used [-Wunused-but-set-variable]
  101 |    int node = -1;
      |        ^~~~

Subtask #1
0 / 30.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 50.0

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