Cod sursa(job #2439149)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 15 iulie 2019 10:45:16
Problema Lazy Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream in ("lazy.in");
ofstream out ("lazy.out");

#define ll long long
#define ld long double
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

struct Edge{
  int id;
  int x;
  int y;
  ll c1;
  ll c2;
  bool operator < (Edge const &a) const{
    if(c1 != a.c1)
      return c1 < a.c1;
    else
      return a.c2 < c2 ;
  }
};

int const nmax = 200000;
vector<Edge> v;
int mult[1 + nmax];

int jump(int val){
  if(mult[val] != val)
    mult[val] = jump(mult[val]);
  return mult[val];
}

void unite(int gala, int galb){
  gala = jump(gala);
  galb = jump(galb);
  mult[gala] = galb;
}

int main()
{
  int n, m;
  in >> n >> m;
  for(int i = 1;i <= n; i++)
    mult[i] = i;

  for(int i = 1;i <= m; i++){
    ll x, y, c1, c2;
    in >> x >> y >> c1 >> c2;
    v.push_back({i, x, y, c1, c2});
  }
  sort(v.begin(), v.end());
  for(int i = 0; i < v.size(); i++){
    Edge e = v[i];
    if(jump(e.x) != jump(e.y)) {
      unite(e.x, e.y);
      out << v[i].id << '\n';
    }
  }
  return 0;
}