Submission #909431

#	Time	Username	Problem	Language	Result	Execution time	Memory
909431		Faisal_Saqib	Toll (APIO13_toll)	C++17	0 / 100	2 ms	6748 KiB

toll

#include <iostream>
#include <vector>
#include <algorithm>
#define pb push_back
using namespace std;
const int N=1e5+10;
int par[N],mx_sz=0,mx_we=0;
pair<int,int> par1[N];
int h[N],sz1[N],val[N];
vector<pair<int,int>> ma[N],ch[N];
void root_at(int x,int p=-1)
{
    sz1[x]=val[x];
    for(auto [w,y]:ma[x])
    {
        if(y!=p)
        {
            h[y]=h[x]+1;
            par1[y]={w,x};
            root_at(y,x);
            sz1[x]+=sz1[y];
        }
    }
}
// void find_mx(int x,int r,int mx=0,int p=-1)
// {
//     if(x==r)
//     {
//         // We fc
//         sz=0;
//         return;
//     }
//     for(auto [w,y]:ma[x])
//     {
//         if(y!=p)
//         {
//             find_mx(y,r,max(mx,w),x);
//         }
//     }
// }
int root(int x)
{
    return (par[x]==x?x:par[x]=root(par[x]));
}
bool join(int x,int y)
{
    x=root(x);
    y=root(y);
    if(x!=y)
    {
        par[x]=y;
        return 1;
    }
    return 0;
}
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        par[i]=i;
    vector<vector<int>> edg;
    for(int j=0;j<m;j++)
    {
        int w,x,y;
        cin>>x>>y>>w;
        edg.pb({w,x,y});
    }
    sort(begin(edg),end(edg));
    for(auto fp:edg)
    {
        if(join(fp[1],fp[2]))
        {
            ma[fp[1]].push_back({fp[0],fp[2]});
            ma[fp[2]].push_back({fp[0],fp[1]});
        }
    }
    vector<pair<int,int>> st;
    while(k--)
    {
        int x,y;
        cin>>x>>y;
        st.pb({x,y});
    }
    for(int i=1;i<=n;i++)
        cin>>val[i];
    root_at(1);
    for(auto [x,y]:st)
    {
        int x1=x;
        int y1=y;
        mx_sz=0;
        mx_we=0;
        while(h[x]!=h[y])
        {
            if(h[x]<h[y])
            {
                if(par1[y].first>mx_we)
                {
                    mx_we=par1[y].first;
                    mx_sz=sz1[y];
                }
                else if(par1[y].first==mx_we)
                {
                    mx_sz=max(mx_sz,sz1[y]);
                }
                y=par1[y].second;
            }
            else
            {
                if(par1[x].first>mx_we)
                {
                    mx_we=par1[x].first;
                    mx_sz=sz1[x];
                }
                else if(par1[x].first==mx_we)
                {
                    mx_sz=max(mx_sz,sz1[x]);
                }
                x=par1[x].second;
            }
        }
        cout<<mx_we*mx_sz<<endl;
    }
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:90:13: warning: unused variable 'x1' [-Wunused-variable]
   90 |         int x1=x;
      |             ^~
toll.cpp:91:13: warning: unused variable 'y1' [-Wunused-variable]
   91 |         int y1=y;
      |             ^~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22