/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 2.77 MiB
#2 Accepted 3ms 2.816 MiB
#3 Accepted 3ms 2.77 MiB
#4 Accepted 4ms 2.77 MiB
#5 Accepted 3ms 2.82 MiB
#6 Accepted 3ms 2.77 MiB
#7 Accepted 6ms 3.02 MiB
#8 Accepted 6ms 2.996 MiB
#9 Accepted 6ms 3.02 MiB
#10 Accepted 6ms 3.191 MiB
#11 Accepted 93ms 10.02 MiB
#12 Accepted 95ms 10.02 MiB
#13 Accepted 95ms 10.02 MiB
#14 Accepted 94ms 10.02 MiB
#15 Accepted 42ms 4.641 MiB
#16 Accepted 42ms 4.52 MiB
#17 Accepted 43ms 4.52 MiB
#18 Accepted 41ms 4.52 MiB
#19 Accepted 42ms 4.48 MiB
#20 Accepted 42ms 4.441 MiB

Code

#include <bits/stdc++.h>
using namespace std;
#define output              freopen("output.txt","w",stdout)
#define input               freopen("input.txt","r",stdin)
///C IO
#define pf                  printf
#define sc                  scanf
#define pch                 putchar
#define ssc                 sscanf
#define spf                 sprintf

///functions
#define pb                  push_back
#define Mid(l,r)            ((l+r)>>1)
#define present(c,x)        ((c).find(x) != (c).end())
#define cpresent(c,x)       (find(all(c),x) != (c).end())
#define mp(x,y)             make_pair(x,y)
#define xx                  first
#define yy                  second
///For loop
#define fr0(i,n)            for(i=0;i<n;i++)
#define fr1(i,n)            for(i=1;i<=n;i++)
#define FOR(a,n)            for(auto a : n)
///memory reset
#define Mem(Array,Val,Size) memset(Array,Val,(Size)*(sizeof(Array[0])))
#define set0(x)             memset(x,0,sizeof(x))
#define setn1(x)            memset(x,-1,sizeof(x))
#define setinf(x)           memset(x,127,sizeof(x))
///misc
#define SZ(v)               ((int) (v).size())
#define all(v)              (v).begin(), (v).end()
///bit operation single variable :: be careful with LL and ULL
#define On(x,i)             (x|=(1<<(i)))
#define Off(x,i)            (x&= ~(1<<(i)))
#define isOn(x,i)           (x&(1<<(i)))
#define Toggle(x,i)         (x^=(1<<(i)))
#define tmod(x,i)           (x&(~(-1<<i)))


///inputs
template <class T> inline void In(T &a){cin>>a;}
template <class T1,class T2> inline void In(T1 &a,T2 &b){cin>>a>>b;}
template <class T1,class T2,class T3> inline void In(T1 &a,T2 &b,T3 &c){cin>>a>>b>>c;}
template <class T1,class T2,class T3,class T4> inline void In(T1 &a,T2 &b,T3 &c,T4 &d){cin>>a>>b>>c>>d;}
inline void Line(string &a){getline(cin,a);}
template <class _T>inline void ina(_T a[],int n){int i; fr0(i,n)In(a[i]);}
///outputs
template <class T> inline void Pr(T a){cout<<a;}
template <class T1,class T2> inline void Pr(T1 a,T2 b){cout<<a<<" "<<b;}
template <class T1,class T2,class T3> inline void Pr(T1 a,T2 b,T3 c){cout<<a<<" "<<b<<" "<<c;}
template <class T1,class T2,class T3,class T4> inline void Pr(T1 a,T2 b,T3 c,T4 d){cout<<a<<" "<<b<<" "<<c<<" "<<d;}

///debug
template <class T> inline void Cr(T a){cerr<<a<<endl;}
template <class T1,class T2> inline void Cr(T1 a,T2 b){cerr<<a<<" "<<b<<endl;}

#define nln                 cout<<"\n"
#define sps cout<<" "
int TEST_CASE=0;
#define tcsp                cout<<"Case "<<(++TEST_CASE)<<": "
#define tcnl                cout<<"Case "<<(++TEST_CASE)<<":\n"
#define FAST                ios_base::sync_with_stdio(false);cin.tie(NULL);
#define precice(n)          cout<<setprecision(n)
#define FIX(n)              cout<<setprecision(n)<<fixed
//data type
typedef long long           ll;
typedef unsigned long long  ull;
typedef long double         LD;
typedef pair<int,int>       pii;
typedef pair<ll,ll>         pll;
typedef pair<double,double> pdd;
typedef vector<int>         vi;



//BIG MOD / mod inverse
template<class _T>inline _T pow(_T a,_T b,_T m) {a%=m;_T ans=1%m;while(b){if(b&1)ans*=a,ans%=m;a*=a;a%=m;b>>=1;}return ans;}
template<class _T>inline _T pow(_T a,_T b)      {_T ans=1;while(b){if(b&1)ans*=a;a*=a;b>>=1;}return ans;}
template<class _T>inline _T add(_T a,_T b,_T m){return a>=m-b?a-(m-b):a+b;}//a,b<m
template<class _T>inline _T multiply(_T a,_T b,_T m){_T ans=0;if(b>a)swap(a,b);while(b){if(b&1)ans=add(ans,a,m);b>>=1;a=add(a,a,m);}return ans;}//a,b<m
template<class _T>inline _T bigpow(_T a,_T b,_T m){a%=m;_T ans=1%m;while(b){if(b&1)ans=multiply(ans,a,m);a=multiply(a,a,m);b>>=1;}return ans;}
template<class _T>inline _T modinvers(_T a,_T m){return m>2000000000LL?bigpow(a,m-2,m):pow(a,m-2,m);}//m is prime
//egcd / mod inverse
template<class _T> _T _egcd(_T a, _T b, _T &x,_T &y){if(!b){x=1,y=0;return a;}_T _g=_egcd(b,a%b,x,y);_T xt=x;x=y,y=xt-(a/b)*y;return _g;}
template<class _T>inline _T fmodinvers(_T a,_T m){_T x,y;_egcd(a,m,x,y);x%=m;if(x<0)x+=m;return x;} //a,m co-prime
template<class _T>inline _T _lcm(_T a, _T b){return (a*b)/__gcd(a,b);}

template <class T> inline  T SQ(T a){return a*a;}
ll SQRT(ll n){ll e=sqrt(n*1.0);ll l=max(0LL,e-2),r=min(n,e+2);ll ans=0;while(l<=r){ll m=Mid(l,r);if(m*m<=n)ans=m,l=m+1;else r=m-1;}return ans;}
ll CBRT(ll n){ll e=cbrt(n*1.0);ll l=max(0LL,e-2),r=min(n,e+2);ll ans=0;while(l<=r){ll m=Mid(l,r);if(m*m*m<=n)ans=m,l=m+1;else r=m-1;}return ans;}
//direction array
/*
knight: int dx[]={1,-1,1,-1,2,2,-2,-2}; int dy[]={2,2,-2,-2,1,-1,1,-1};
Grid Side: int dx[]={0,0,1,-1,};int dy[]={1,-1,0,0};
*/
///constant
const LD EPS =              1e-9;
const LD PI=                acos(-1.0);
const int SIZE=             1e5+5;
ll mod=                     1e9+7;

vi adj[SIZE];
int heavy[SIZE];
int par[SIZE];
int calcheavy(int u,int p)
{
    par[u]=p;
    int s=1,h=-1,hs=0;

    for(int v: adj[u])
    {
        if(v!=p)
        {
            int vs=calcheavy(v,u);
            s+=vs;
            if(vs>hs)hs=vs,h=v;
        }
    }
    heavy[u]=h;
    return s;
}
int cn,sn;
int num[SIZE],chain[SIZE],head[SIZE],jump[SIZE];
void makechain(int u,int p)
{
    chain[u]=cn;
    num[u]=sn++;
    int h=heavy[u];
    if(h!=-1)makechain(h,u);
    else cn++;
    for(int v:adj[u])
    {
        if(v!=p && v!=h)
        {
            head[cn]=v;
            jump[cn]=u;
            makechain(v,u);
        }
    }
}
int val[SIZE];
int n;
int tree[3*SIZE];
int query(int l,int r)
{
    r++;
    int mx=0;
    for(l+=n,r+=n;l<r;l>>=1,r>>=1)
    {
        if(l&1)mx=max(mx,tree[l++]);
        if(r&1)mx=max(mx,tree[--r]);

    }
    return mx;
}

int U[SIZE],V[SIZE],C[SIZE],u,v,tc,q;
int main()
{
    FAST

    {
        In(n,q);

        for(int i=1;i<=n;i++)adj[i].clear();
        for(int i=1;i<n;i++)
        {
            In(U[i],V[i],C[i]);
            adj[U[i]].pb(V[i]);
            adj[V[i]].pb(U[i]);
        }
        cn=sn=0;
        calcheavy(1,0);
        makechain(1,0);
        //if(sn!=n)assert(0);
        ///assign value
        for(int i=1;i<n;i++)
        {
            u=U[i];
            v=V[i];
            if(par[u]==v)
            {
                val[u]=C[i];
            }else val[v]=C[i];
            //cerr<<u<<"  "<<v<< "   "<<par[u]<<"  "<<par[v]<<endl;
            //Cr(val[u],val[v]);
        }
        ///make segment tree

        for(int i=0;i<n;i++)
        {
            tree[num[i+1]+n]=val[i+1];
            //cerr<<val[i+1]<<endl;
        }
        for(int i=n-1;i>0;i--)tree[i]=max(tree[i<<1],tree[i<<1|1]);

        //for(int i=1;i<2*n;i++)cerr<<i<<"  "<<tree[i]<<endl;
        while(q--)
        {

            {
                In(u,v);
                int mx=0;
                while(chain[u]!=chain[v])
                {
                    if(chain[u]>chain[v])
                    {
                        mx=max(mx,query(num[head[chain[u]]],num[u]));
                        u=jump[chain[u]];
                    }else
                    {
                        mx=max(mx,query(num[head[chain[v]]],num[v]));
                        v=jump[chain[v]];
                    }
                }

                mx=max(mx,query(min(num[u],num[v])+1,max(num[u],num[v])));
                Pr(mx);nln;
            }


        }



    }



    return 0;
}

Information

Submit By
Type
Submission
Problem
P1019 Graph Stuff
Language
C++17 (G++ 13.2.0)
Submit At
2024-01-03 16:18:14
Judged At
2024-10-20 23:39:11
Judged By
Score
100
Total Time
95ms
Peak Memory
10.02 MiB