Submission #62544450


Source Code Expand

/*
Author : Mikira
Sat 08 Feb 2025 08:43:16 PM HKT
*/

#include "bits/stdc++.h"
using namespace std;

typedef long long LL;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<LL, LL> PLL;
typedef pair<LL, LL> pll;
typedef long double ld;

#define rep(i, a, b) for(int i = a; i < int(b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define popf pop_front
#define pf push_front
#define popb pop_back
#define pb push_back
#define fi first
#define se second

const double EPS = 1e-9;
const int INFMEM = 63;

// Do dir^1 to get reverse direction
const int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
const int dy[8] = {1, -1, 0, 0, 1, -1, -1, 1};
const char dch[4] = {'R', 'L', 'D', 'U'};

// Do (dir + 2)%4 to get reverse direction
// const int dx[8] = {-1,0,1,0,-1,1,1,-1};
// const int dy[8] = {0,1,0,-1,1,1,-1,-1};
// const char dch[4] = {'U','R','D','L'};
const double PI = 3.141592653589793;

inline void fasterios() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
}
#define endl '\n'
const int MOD = 1000000007;
// const int MOD = 998244353;
using Edge = pair <LL, pair<LL, LL>>;

struct UF {
  vi e;
  UF(int n) : e(n + 1, -1) {}
  bool sameSet(int a, int b) { return find(a) == find(b); }
  int size(int x) { return -e[find(x)]; }
  int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
  bool join(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;
    if (e[a] > e[b]) swap(a, b);
    e[a] += e[b]; e[b] = a;
    return true;
  }
};

int main() {
  fasterios();
  int m;
  int n; cin >> n >> m;
  vector <Edge> edges(m);
  int idx = 1;
  vector <Edge> notUsed;
  UF solver(n + 5);
  LL connected = 0;
  trav(cur, edges) {
    cur.fi = idx++;
    cin >> cur.se.fi >> cur.se.se;
    if (!solver.join(cur.se.fi, cur.se.se)) notUsed.push_back(cur);
    else connected++;
  }
  set <LL> released;
  rep(i, 1, n + 1) {
    released.insert(solver.find(i));
  }
  LL needed = (n - 1) - connected;
  vector <Edge> ans;
  for (int i = 0; i < needed; ++i) {
    LL currentParent = solver.find(notUsed[i].se.fi);
    auto currentBegin = *released.begin();
    if (currentBegin == currentParent) {
      currentBegin = *std::next(released.begin());
    }
    ans.pb(notUsed[i]);
    ans.back().se.se = currentBegin;
    solver.join(currentParent, currentBegin);
    LL deleted = currentParent;
    if (solver.find(currentParent) == currentParent) {
      deleted = currentBegin;
    }
    released.erase(deleted);
  }
  cout << ans.size() << endl;
  trav(cur, ans) {
    cout << cur.fi << " " << cur.se.fi << " " << cur.se.se << endl;
  }
}

Submission Info

Submission Time
Task E - Cables and Servers
User hocky
Language C++ 20 (gcc 12.2)
Score 450
Code Size 2857 Byte
Status AC
Exec Time 95 ms
Memory 31992 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 3
AC × 22
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
random_01.txt AC 17 ms 7904 KiB
random_02.txt AC 15 ms 12644 KiB
random_03.txt AC 2 ms 3556 KiB
random_04.txt AC 1 ms 3520 KiB
random_05.txt AC 22 ms 13628 KiB
random_06.txt AC 17 ms 13660 KiB
random_07.txt AC 4 ms 3900 KiB
random_08.txt AC 1 ms 3516 KiB
random_09.txt AC 19 ms 8180 KiB
random_10.txt AC 9 ms 8384 KiB
random_11.txt AC 33 ms 10300 KiB
random_12.txt AC 1 ms 3476 KiB
random_13.txt AC 26 ms 8548 KiB
random_14.txt AC 26 ms 8564 KiB
random_15.txt AC 26 ms 8528 KiB
random_16.txt AC 26 ms 8632 KiB
random_17.txt AC 95 ms 20076 KiB
random_18.txt AC 93 ms 31992 KiB
random_19.txt AC 2 ms 3592 KiB
sample_01.txt AC 1 ms 3540 KiB
sample_02.txt AC 1 ms 3416 KiB
sample_03.txt AC 1 ms 3480 KiB