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 |
|
|
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 |