This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "simurgh.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
int m = u.size();
vii seen(m);
rep(i, m) {
if (!seen[i]) {
vii curr[3];
vii parent(n, -1);
function<int(int)> root;
root = [&](int x) {
if (parent[x] < 0) {
return x;
}
return parent[x] = root(parent[x]);
};
vii query;
rep(j, m) {
int ru = root(u[j]), rv = root(v[j]);
if (ru == rv) {
continue;
}
if ((root(u[i]) == ru && root(v[i]) == rv) || (root(u[i]) == rv && root(v[i]) == ru)) {
curr[seen[j]].emplace_back(j);
continue;
}
if (parent[ru] < parent[rv]) {
swap(ru, rv);
}
parent[rv] += parent[ru];
parent[ru] = rv;
query.emplace_back(j);
}
if (curr[0].size() == 1 && curr[1].empty() && curr[2].empty()) {
seen[curr[0][0]] = 2;
continue;
}
vii ans;
int amax = 0, amin = n;
forin(x, curr[0]) {
query.emplace_back(x);
ans.emplace_back(count_common_roads(query));
amax = max(amax, ans.back());
amin = min(amin, ans.back());
query.pop_back();
}
if (amin == amax) {
if (!curr[1].empty()) {
query.emplace_back(curr[1][0]);
amin = count_common_roads(query);
amax = amin + 1;
} else if (!curr[2].empty()) {
query.emplace_back(curr[2][0]);
amax = count_common_roads(query);
}
}
rep(j, curr[0].size()) {
if (ans[j] == amax) {
seen[curr[0][j]] = 2;
} else {
seen[curr[0][j]] = 1;
}
}
}
}
vii res;
rep(i, m) {
if (seen[i] == 2) {
res.emplace_back(i);
}
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |