/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 18ms 11.961 MiB
#2 Wrong Answer 81ms 20.23 MiB
#3 Wrong Answer 94ms 20.309 MiB

Code

/*If we keep holding onto yesterday, what are we going to be tomorrow?*/
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#include <bits/stdc++.h> // DON'T WATCH THE CLOCK; DO WHAT IT DOES.  KEEP GOING.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

//============================================== Speed
#define fast_IO ios_base::sync_with_stdio(0), cin.tie(0)
//============================================== Aliases Or TypeDEf
#define ll long long
#define ld long double
#define ull unsigned long long
#define pl pair<ll, ll>
//============================================== Macros
#define ff first
#define ss second
#define fl(i,n) for(int i=0;i<n;i++)
#define no cout << "NO" << endl
#define yes cout << "YES" << endl
#define imp cout << "IMPOSSIBLE" << endl
#define all(x) x.begin(), x.end()
#define allr(a) a.rbegin(), a.rend()
#define gc getchar_unlocked
#define endl '\n'
#define coutd cout << fixed << setprecision(15) // coutd<<res<<endl;
#define mem(a, b) memset(a, b, sizeof(a))
//============================================== Debug
#define deb(x) cout << #x << "  =  " << x << endl
#define deb2(x, y) cout << #x << "  =  " << x << "  ,  " << #y << "  =  " << y << endl
#define deb3(x, y, z) cout << #x << "  =  " << x << "  ,  " << #y << "  =  " << y << "  ,  " << #z << "  =  " << z << endl
#define deb4(x, y, z, w) cout << #x << "  =  " << x << "  ,  " << #y << "  =  " << y << "  ,  " << #z << "  =  " << z << "  ,  " << #w << "  =  " << w << endl
//============================================== Operator overloads
namespace io{

    template<typename First, typename Second> istream& operator >> ( istream &is, pair<First, Second> &p ) { return is >> p.first >> p.second; }// cin >> pair<T1, T2>
    template<typename First, typename Second> ostream& operator << ( ostream &os, const pair<First, Second> &p ) { return os << p.first << " " << p.second; }// cout << pair<T1, T2>

    template<typename First> istream& operator >> ( istream &is, vector<First> &v ) { for( First &x : v ) { is >> x; } return is; }// cin >> vector<T>
    template<typename First> ostream& operator << ( ostream &os, const vector<First> &v ) { bool space = false; for( First x : v ) { if( space ) os << " "; space = true; os << x; } return os; }// cout << vector<T>
    
    template<typename First> ostream& operator << ( ostream &os, const set<First> &st ) { bool space = false; for( First x : st ) { if( space ) os << " "; space = true; os << x; } return os; } // cout << set<T>
    template<typename First> ostream& operator << ( ostream &os, const multiset<First> &st ) { bool space = false; for( First x : st ) { if( space ) os << " "; space = true; os << x; } return os; } // cout << multiset<T>
    template<typename First, typename Second> ostream& operator << ( ostream &os, const map<First, Second> &mp ) { for( auto it : mp ) { os << it << endl;  } return os; } // cout << map<T1, T2> 

} using namespace io;
//============================================== Utility functions
template <typename T>
void print(T &&t)  { cout << t << "\n"; }
void printarr(ll arr[], ll n){fl(i,n) cout << arr[i] << " ";cout << "\n";}
template<typename T>
void printvec(vector<T>v){ll n=v.size();fl(i,n)cout<<v[i]<<" ";cout<<"\n";}
template<typename T>
ll sumvec(vector<T>v){ll n=v.size();ll s=0;fl(i,n)s+=v[i];return s;}
//============================================== EXT. STL
template <typename T> using PQ = priority_queue<T>;
template <typename T> using QP = priority_queue<T,vector<T>,greater<T>>;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;// ordered_set<ll> st;st.order_of_key(x) // number of elements < x ; *(st.find_by_order(x))  (x)th largest element
template <typename T> using ordered_multiset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <typename T,typename R> using ordered_map = tree<T, R , less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T,typename R> using ordered_multimap = tree<T, R , less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
//============================================== Mathematical functions
inline ll Ceil(ll p, ll q)  {return p < 0 ? p / q : p / q + !!(p % q);}
inline ll Floor(ll p, ll q) {return p > 0 ? p / q : p / q - !!(p % q);}
inline double logb(ll base,ll num){ return (double)log(num)/(double)log(base);}
double euclidean_distance(ll x1,ll y1,ll x2,ll y2){double a=(x2-x1)*(x2-x1);double b=(y2-y1)*(y2-y1);double c=(double)sqrt(a+b);return c;}
ll __lcm(ll a, ll b){return (a/__gcd(a,b)*b);}
ll BigMod (ll b, ll p, ll m) {if (p == 0) return 1; if (p % 2 == 0) {ll s = BigMod(b, p / 2, m); return ((s % m) * (s % m)) % m;} return ((b % m) * (BigMod(b, p - 1, m) % m)) % m;}
ll ModInv (ll b, ll m) {return BigMod(b, m - 2, m);}
//>>Check
bool isPrime(ll n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
bool isPowerOfTwo(int n){if(n==0)return false;return (ceil(log2(n)) == floor(log2(n)));}
bool isPerfectSquare(ll x){if (x >= 0) {ll sr = sqrt(x);return (sr * sr == x);}return false;}
//============================================== Bits
#define Set(x, k) (x |= (1LL << k))
#define Unset(x, k) (x &= ~(1LL << k))
#define Check(x, k) (x & (1LL << k))
#define Toggle(x, k) (x ^= (1LL << k))
int popcount(ll x){return __builtin_popcountll(x);};
int poplow(ll x){return __builtin_ctzll(x);};
int pophigh(ll x){return 63 - __builtin_clzll(x);};
//>>Convert
string decToBinary(int n){string s="";int i = 0;while (n > 0) {s =to_string(n % 2)+s;n = n / 2;i++;}return s;}
ll binaryToDecimal(string n){string num = n;ll dec_value = 0;int base = 1;int len = num.length();for(int i = len - 1; i >= 0; i--){if (num[i] == '1')dec_value += base;base = base * 2;}return dec_value;}
//============================================== Global_Constants
const ll N = 500050;
const ll INF = 1e18 + 10;
const ull mod = 1e9 + 7;
//==============================================  user define function  ==============================================//

//  ██████   █████  ██    ██ ███████ ███    ███
//  ██      ██   ██  ██  ██  ██      ████  ████
//  ██████  ███████   ████   █████   ██ ████ ██
//      ██  ██   ██    ██    ██      ██  ██  ██
//  ██████  ██   ██    ██    ███████ ██      ██
ll n, m , a , b;
    vector<ll> adj[N], vis(N) , vis1(N) , vis2(N);
    ll dis[N], dis1[N],dis2[N] , node;ll mx = 0;ll node1 , node2;
void Sayem(ll tc)
{
    /// out side
    
    
    /// in side 0.1
    cin >> n;
    m = n - 1;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    // cout << n << endl;
    queue<int> q;
    q.push(1);
    vis[1] = true;
    dis[1] = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto v : adj[u])
        {
            if (!vis[v])
            {
                q.push(v);
                dis[v] = dis[u] + 1;
                vis[v] = true;
            }
        }
    }
    
    for(int i = 1 ; i <= n ; i ++){
        mx = max(mx , dis[i]); 
    }
    
    for(int i = 1 ; i <= n ; i ++){
        if(mx == dis[i]){
            node1 = i;
            break;
        } 
    } 
    // for(int i = 1 ; i <= n ; i ++){
    //     deb2(i , dis[i]);
    // }
    // deb2(mx , node1); 
    ///
    q.push(node1);
    vis1[node1] = true;
    dis1[node1] = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto v : adj[u])
        {
            if (!vis1[v])
            {
                q.push(v);
                dis1[v] = dis1[u] + 1;
                vis1[v] = true;
            }
        }
    }
    mx = 0;
    for(int i = 1 ; i <= n ; i ++){
        mx = max(mx , dis1[i]); 
    }
    for(int i = 1 ; i <= n ; i ++){
        if(mx == dis1[i]){
            node2 = i;
            break;
        } 
    }
    // for(int i = 1 ; i <= n ; i ++){
    //     deb2(i , dis1[i]);
    // }
    // deb2(mx , node2); 
    ///
    q.push(node2);
    vis2[node2] = true;
    dis2[node2] = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto v : adj[u])
        {
            if (!vis2[v])
            {
                q.push(v);
                dis2[v] = dis2[u] + 1;
                vis2[v] = true;
            }
        }
    }
    mx = 0;
    for(int i = 1 ; i <= n ; i ++){
        if(dis1[i] == dis2[i])
        mx = max(mx , dis2[i]); 
    }
    for(int i = 1 ; i <= n ; i ++){
        if(mx == dis2[i] && mx == dis1[i]){
            node = i;
            break;
        } 
    }
    ///
    for(int i = 0 ; i < N ; i++){
        vis[i] = 0 , dis[i];
    }
    // deb(node);
    q.push(node);
    vis[node] = true;
    dis[node] = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto v : adj[u])
        {
            if (!vis[v])
            {
                q.push(v);
                dis[v] = dis[u] + 1;
                vis[v] = true;
            }
        }
    }
    mx = 0;
    for(int i = 1 ; i <= n ; i ++){
        mx = max(mx , dis[i]); 
    }
    
    // for(int i = 1 ; i <= n ; i++){
    //     deb4(i , dis[i] , dis1[i] , dis2[i]);
    // }
   cout << mx << " " << node << endl;



    
    
    
    return;
}

//===================================================   STOP   =======================================================//

/* Hey you should check this out
    * int overflow, array bounds
    * reset global array and variable
    * look for special cases (n=1?)
    * do something instead of nothing and stay organized
    * bruteforce to find pattern
    * DON'T GET STUCK ON ONE APPROACH
    * Think the problem backwards
    * In practice time don't see failing test case
*/

int32_t main()
{
    fast_IO;
    int _TB = 1, tc = 1;
    // cin >> _TB;
    while (_TB--)
    {
        Sayem(tc++);
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1069 Vaccination
Contest
Brain Booster #4
Language
C++20 (G++ 13.2.0)
Submit At
2024-07-14 17:41:42
Judged At
2024-11-11 03:22:45
Judged By
Score
5
Total Time
94ms
Peak Memory
20.309 MiB