e52b4d - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>

#define int long long

#define debug     cout << "ok\n";
#define SQR(x)    (1LL * ((x) * (x)))
#define MASK(i)   (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi        first
#define se        second
#define pb        push_back

#define mp make_pair
#define pii pair<int,int>
#define pli pair<ll,int>
#define vi vector<int>

#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int ui;

using namespace std;

const int M = 1e9 + 7;
const int INF = 1e9 + 7;
const ll INFLL = (ll)2e18 + 7LL;
const ld PI = acos(-1);

const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};

template<class _, class __>
    bool minimize(_ &x, const __ y){
        if(x > y){
            x = y;
            return true;
        } else return false;
    }
template<class _, class __>
    bool maximize(_ &x, const __ y){
        if(x < y){
            x = y;
            return true;
        } else return false;
    }

template<class _,class __>
    void Add(_ &x, const __ y) {
        x += y;
        if (x >= M) {
            x -= M;
        }
        return;
    }

template<class _,class __>
    void Diff(_ &x, const __ y) {
        x -= y;
        if (x < 0) {
            x += M;
        }
        return;
    }

//--------------------------------------------------------------

const int MaxN = 1e5+7;

int n,m,q,res[MaxN];
set<int> s[MaxN];

struct Edges {
    int u;
    int v;
    int w;
} edge[MaxN];

bool cmp(Edges a,Edges b) {
    return a.w < b.w;
}

struct Query {
    int u;
    int v;
    int k;
    int cs;
} que[MaxN],que_tmp[MaxN];

struct DSU {
    stack<pii> st1;
    stack<pii> st2;

    int n;
    vi lab;

    void Set(int _n) {
        n = _n;
        lab.resize(n+1,-1);
    }

    int GR(int u) {
        return lab[u] < 0 ? u : GR(lab[u]);
    }

    pii history() {
        return mp(st1.size(),st2.size());
    }

    void uni(int u,int v) {
        u = GR(u);
        v = GR(v);
        if (u == v) return;
        st1.push(mp(u,lab[u]));
        st1.push(mp(v,lab[v]));
        if (lab[u] < lab[v]) {
            lab[u] += lab[v];
            lab[v] = u;
            for (int x : s[v]) {
                if (s[u].find(x) == s[u].end()) {
                    s[u].insert(x);
                    st2.push(mp(u,x));
                }
            }
        }
        else {
            lab[v] += lab[u];
            lab[u] = v;
            for (int x : s[u]) {
                if (s[v].find(x) == s[v].end()) {
                    s[v].insert(x);
                    st2.push(mp(v,x));
                }
            }
        }
    }

    void rollback(pii tmp) {
        while (st1.size() > tmp.fi) {
            int u = st1.top().fi;
            int v = st1.top().se;
            lab[u] = v;
            st1.pop();
        }
        while (st2.size() > tmp.se) {
            int u = st2.top().fi;
            int v = st2.top().se;
            s[u].erase(v);
            st2.pop();
        }
    }
} dsu;

void dnc(int l,int r,int ls,int rs) {
    if (l > r || ls > rs) return;
    int mid = (l+r) >> 1;
    pii tmp = dsu.history();
    for (int i=l;i<=mid;i++) {
        dsu.uni(edge[i].u,edge[i].v);
    }
    int lss = ls - 1;
    int rss = rs + 1;
    for (int i=ls;i<=rs;i++) {
        int u = que[i].u;
        int v = que[i].v;
        int k = que[i].k;
        int cs = que[i].cs;
        u = dsu.GR(u);
        v = dsu.GR(v);
        if (u != v || s[u].size() < k) {
            que_tmp[--rss] = que[i];
        }
        else {
            minimize(res[cs],edge[mid].w);
            que_tmp[++lss] = que[i];
        }
    }
    for (int i=ls;i<=rs;i++) que[i] = que_tmp[i];
    dnc(mid+1,r,rss,rs);
    dsu.rollback(tmp);
    dnc(l,mid-1,ls,lss);
}

void sol() {
    cin >> n >> m >> q;
    dsu.Set(n);
    for (int i=1;i<=n;i++) {
        int x;
        cin >> x;
        s[i].insert(x);
    }
    for (int i=1;i<=m;i++) {
        int u,v,k;
        cin >> u >> v >> k;
        edge[i] = (Edges){u,v,k};
    }
    sort(edge+1,edge+m+1,cmp);
//    for (int i=1;i<=m;i++) cout << edge[i].u << ' ' << edge[i].v << ' ' << edge[i].w << '\n';
    memset(res,0x3f,sizeof(res));
    for (int i=1;i<=q;i++) {
        int u,v,k;
        cin >> u >> v >> k;
        if (u == v && k == 1) res[i] = 0;
        que[i] = (Query){u,v,k,i};
    }
    dnc(1,m,1,q);
    for (int i=1;i<=q;i++) cout << res[i] << '\n';
}

signed main() {
    freopen("test.inp","r",stdin);
//    freopen("TRAVEL.inp","r",stdin);
//    freopen("TRAVEL.out","w",stdout);
    FAST
    int t=1;
//    cin >> t;
    while (t--) sol();
}