Submission #3043781

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <random>
#include <fstream>
#include <string>
#include <tuple>
#include <deque>
#include <set>
#include <map>
#include <stack>

#define REP(i, N) for(int i = 0; i< N; i++)
using namespace std;
#define ll long long
const int INF = 1 << 29;
const ll llINF = 10000000000000000;

const int MOD = 1000000007;

#define MAX_N 100100
typedef pair<int, int> P;
typedef pair<ll, ll> llP;

class UnionFindTree{
private:
    int par[MAX_N];
    int urank[MAX_N];
    int size[MAX_N];
public:
    int init(int n);
    int find(int x);
    int unite(int x, int y);
    int same(int x, int y);
    int parnum(int x){return par[x];}
    int ranknum(int x){return urank[x];}
    int sizenum(int x){return size[find(x)];}
};

int UnionFindTree::init(int n){
    REP(i, n){
        par[i] = i;
        urank[i] = 0;
        size[i] = 1;
    }
    return 0;
}

int UnionFindTree::find(int x){
    if(par[x] == x)return x;
    else return par[x] = find(par[x]);
}

int UnionFindTree::unite(int x, int y){
    x = find(x);
    y = find(y);
    
    if(x == y)return 0;
    if(urank[x] < urank[y]){
        par[x] = y;
        size[y] += size[x];
    }else{
        par[y] = x;
        size[x] += size[y];
        if(urank[x] == urank[y])urank[x] ++;
    }
    return 0;
}

int UnionFindTree::same(int x, int y){
    return find(x) == find(y);
}

struct edge{int u, v, cost;};
bool comp(const edge& e1, const edge& e2){
    return e1.cost < e2.cost;
}

int mediantree(int V, int E){
    int median = 0;
    vector<int> edgescost;
    vector<edge> es;
    REP(i, E){
        int s, t, w;
        cin >> s >> t >> w;
        es.push_back(edge{s, t, w});
    }
    sort(es.begin(), es.end(), comp);
    UnionFindTree tree;
    tree.init(V);
    int nagasa = 0;
    REP(i, E){
        edge e = es[i];
        if(!tree.same(e.u, e.v)){
            tree.unite(e.u, e.v);
            edgescost.push_back(e.cost);
            nagasa++;
        }
    }
    if(nagasa % 2 == 0)median = (edgescost[nagasa/2] + edgescost[nagasa/2 + 1]) / 2;
    else median = edgescost[(nagasa - 1) / 2];
    return median;
}

struct point{int number, x, y;};

bool xjisho(const point& p1, const point& p2){
    return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}
bool yjisho(const point& p1, const point& p2){
    return p1.y < p2.y || (p1.y == p2.y && p1.x < p2.x);
}

int mahounoito(){
    vector<edge> es1;
    int V, E;
    cin >> V >> E;
    REP(i, E){
        int s, t, w;
        cin >> s >> t >> w;
        es1.push_back(edge{s, t, w});
    }
    int Q;
    int res = 0;
    cin >> Q;
    UnionFindTree queries;
    queries.init(V);
    int query = 0;
    vector<int> ress;
    vector<P> tunagattenai;
    vector<edge> es;
    REP(query, Q){
        int p,q;
        cin >> p >> q;
        queries.unite(p, q);
        tunagattenai.push_back(P(p,q));
        REP(i, es1.size()){
            if(queries.same(es1.back().u, es1.back().v)){
                es.push_back(es1.back());
                es1.pop_back();
            }
        }
        sort(es.begin(), es.end(), comp);
        UnionFindTree tree;
        tree.init(V);
        res = 0;
        REP(i, es.size()){
            edge e = es[i];
            if(!tree.same(e.u, e.v)){
                tree.unite(e.u, e.v);
                res += e.cost;
            }
        }
        bool ok = true;
        REP(i, tunagattenai.size()){
            if(tree.same(tunagattenai.back().first, tunagattenai.back().second))tunagattenai.pop_back();
            else ok = false;
        }
        if(ok)ress.push_back(res);
        else ress.push_back(-1);
    }
    REP(i, ress.size()){
        if(ress[i] == -1)printf("IMPOSSIBLE\n");
        else printf("%d\n", ress[i]);
    }
    return res;
}

int gameonagrid(){
    vector<edge> es;
    int H, W, S, G;
    cin >> H >> W;
    int Sx, Sy, Gx, Gy;
    cin >> Sx >> Sy;
    S = Sx + Sy * W;
    cin >> Gx >> Gy;
    G = Gx + Gy * W;
    int P[10100] = {0};
    int res = 0;
    REP(i, W * H){
        int p;
        cin >> p;
        P[i] = -p;
        res += P[i];
    }
    REP(i, H * W){
        if(i >= W){
            es.push_back(edge{i, i - W, -P[i] * P[i - W]});
            es.push_back(edge{i - W, i, -P[i] * P[i - W]});
        }
        if(i < (H - 1) * W){
            es.push_back(edge{i, i + W, -P[i] * P[i + W]});
            es.push_back(edge{i + W, i, -P[i] * P[i + W]});
        }
        if(i % W != 0){
            es.push_back(edge{i, i - 1, -P[i] * P[i - 1]});
            es.push_back(edge{i - 1, i, -P[i] * P[i - 1]});
        }
        if(i % W != W - 1){
            es.push_back(edge{i, i + 1, -P[i] * P[i + 1]});
            es.push_back(edge{i + 1, i, -P[i] * P[i + 1]});
        }
    }
    
    sort(es.begin(), es.end(), comp);
    UnionFindTree tree;
    tree.init(W * H);
    REP(i, es.size()){
        edge e = es[i];
        if(!tree.same(e.u, e.v)){
            tree.unite(e.u, e.v);
            res += e.cost;
        }
    }
    return -res;
}

int built(){
    vector<point> town;
    vector<edge> es;
    int N, E;
    cin >> N;
    E = 2 * (N - 1);
    REP(i, N){
        int x, y;
        cin >> x >> y;
        town.push_back(point{i,x,y});
    }
    sort(town.begin(), town.end(), xjisho);
    REP(i, N - 1){
        es.push_back(edge{town[i].number, town[i + 1].number, min(abs(town[i].x - town[i + 1].x),abs(town[i].y - town[i + 1].y))});
    }
    sort(town.begin(), town.end(), yjisho);
    REP(i, N - 1){
        es.push_back(edge{town[i].number, town[i + 1].number, min(abs(town[i].x - town[i + 1].x),abs(town[i].y - town[i + 1].y))});
    }
    sort(es.begin(), es.end(), comp);
    UnionFindTree tree;
    tree.init(N);
    int res = 0;
    REP(i, E){
        edge e = es[i];
        if(!tree.same(e.u, e.v)){
            tree.unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}


int kruskal(){
    vector<edge> es;
    int V, E;
    cin >> V >> E;
    REP(i, E){
        int s, t, w;
        cin >> s >> t >> w;
        es.push_back(edge{s, t, w});
    }
    sort(es.begin(), es.end(), comp);
    UnionFindTree tree;
    tree.init(V);
    int res = 0;
    REP(i, E){
        edge e = es[i];
        if(!tree.same(e.u, e.v)){
            tree.unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}

int prim(){
    struct edge {int to, cost;};
    vector<edge> e[MAX_N];
    int mincost[MAX_N];
    bool used[MAX_N];
    int N, E;
    cin >> N >> E;
    REP(i, N){
        mincost[i] = INF;
        used[i] = false;
    }
    REP(i, E){
        int s, t, w;
        cin >> s >> t >> w;
        edge ss = {t, w};
        edge tt = {s, w};
        e[s].push_back(ss);
        e[t].push_back(tt);
    }
    mincost[0] = 0;
    int res = 0;
    priority_queue<P, vector<P>, greater<P>> que;
    REP(i, e[0].size()){
        que.push(P(e[0][i].cost,e[0][i].to));
    }
    used[0] = true;
    int vnokazu = 1;
    while(vnokazu < N){
        P p;
        do{
            p = que.top();que.pop();
        }while(used[p.second]);
        used[p.second] = true;
        res += p.first;
        vnokazu++;
        REP(i, e[p.second].size()){
            if(!used[e[p.second][i].to])que.push(P(e[p.second][i].cost,e[p.second][i].to));
        }
    }
    return res;
}

int main(){
    mahounoito();
}

Submission Info

Judge Result