LightOJ 1101 Solution

on

#include<bits/stdc++.h>
#define mx 50110
#define ll long long
#define pii pair<int, int>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

struct str
{
    int u, v, w;
};

int level[mx], parent[mx], father[mx], rnk[mx], st[17][mx], maxi[17][mx];
vector<pii>a[mx];
vector<str>v, mst;

bool compare(str a, str b)
{
    return a.w < b.w;
}

int finds(int x)
{
    if(father[x] == x)
        return x;

    return father[x] = finds(father[x]);
}

int unions(int a, int b, int w)
{
    int u = finds(a);
    int v = finds(b);

    if(u == v)
        return 0;
    else
    {
        if(rnk[u] < rnk[v])
            father[u] = father[v];
        else
        {
            rnk[u] = max(rnk[u], rnk[v]+1);
            father[v] = father[u];
        }

        return w;
    }
}

void kruskal(int node)
{
    for(int i=0;i<=node;i++)
        father[i] = i;

    sort(v.begin(), v.end(), compare);
    for(int i=0;i<v.size();i++)
    {
        int s = unions(v[i].u, v[i].v, v[i].w);

        if(s > 0)
            mst.push_back(v[i]);
    }
}

void dfs(int from, int node, int depth, int weight)
{
    parent[node] = from;
    level[node] = depth;
    maxi[0][node] = weight;

    for(int i=0; i<a[node].size();i++)
    {
        pii next = a[node][i];

        if(next.first == from)
            continue;

        dfs(node, next.first, depth+1, next.second);
    }
}

void initialize(int n)
{
    for(int i=0;i<n;i++)
        st[0][i] = parent[i];

    for(int k=1; k<16; k++)
    {
        for(int i=0; i<n; i++)
        {
            if(st[k-1][i] != -1)
            {
                int j = st[k-1][i];
                st[k][i] = st[k-1][j];
                maxi[k][i] = max(maxi[k-1][i], maxi[k-1][j]);
            }
        }
    }
}

int query(int p, int q)
{
    if(level[p] < level[q])
        swap(p, q);

    int log = 1;
    while(1)
    {
        int next = log+1;

        if((1<<next) > level[p])
            break;

        log++;
    }

    int maximum = 0;
    for(int i=log; i>=0; i--)
    {
        if(level[p] - (1<<i) >= level[q])
        {
            maximum = max(maximum, maxi[i][p]);
            p = st[i][p];
        }
    }

    if(p == q)
        return maximum;

    for(int i=log; i>=0; i--)
    {
        if(st[i][p] != -1 && st[i][p] != st[i][q])
        {
            maximum = max(maximum, maxi[i][p]);
            maximum = max(maximum, maxi[i][q]);

            p = st[i][p];
            q = st[i][q];
        }
    }

    maximum = max(maximum, maxi[0][p]);
    maximum = max(maximum, maxi[0][q]);

    return maximum;
}

void clears()
{
    for(int i=0;i<mx;i++)
        level[i] = parent[i] = father[i] = rnk[i] = 0, a[i].clear();

    v.clear();
    mst.clear();

    for(int i=0; i<16; i++)
    {
        for(int j=0; j<mx; j++)
            st[i][j] = -1, maxi[i][j] = 0;
    }
}

int main()
{
    fast

    int t, k = 1;
    cin >> t;

    while(t--)
    {
        int n, m, x, y, w;
        cin >> n >> m;

        for(int i=1; i<=m; i++)
        {
            cin >> x >> y >> w;
            x--, y--;

            v.push_back({x, y, w});
        }

        kruskal(n);

        for(int i=0; i<mst.size(); i++)
        {
            x = mst[i].u;
            y = mst[i].v;
            w = mst[i].w;
            
            a[x].push_back(pii(y, w));
            a[y].push_back(pii(x, w));
        }

        dfs(-1, 0, 0, 0);
        initialize(n);

        int q;
        cin >> q;

        cout << "Case " << k++ << ":\n";
        while(q--)
        {
            cin >> x >> y;
            x--, y--;

            cout << query(x, y) << "\n";
        }

        clears();
    }

    return 0;
}

Comments

Post a Comment