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 <bits/stdc++.h>
#define int int64_t
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ar = array<int, 2>;
const int64_t INF = 1ll << 60;
const int N = 3e5 + 5;
namespace dsu {
int dpr[N];
int gpr(int x) {
return dpr[x] == x ? x : dpr[x] = gpr(dpr[x]);
}
void merge(int u, int v) {
dpr[gpr(u)] = gpr(v);
}
}
int st[N], fn[N], T, pr[N], up[N], mn[N], W[N], n, m;
ar E[N];
bool ok[N];
vector<int> ad[N];
vector<ar> adj[N];
bool is_p(int p, int v) {
return st[p] <= st[v] && fn[v] <= fn[p];
}
void dfs(int v) {
st[v] = T++;
for (auto [u, id]: adj[v]) if (u != pr[v]) {
up[u] = id;
pr[u] = v;
dfs(u);
}
fn[v] = T;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
FOR(i, 0, m) {
cin >> E[i][0] >> E[i][1];
--E[i][0], --E[i][1];
}
FOR(i, 1, n) {
int x; cin >> x; --x;
auto [u, v] = E[x];
adj[v].push_back({u, x});
adj[u].push_back({v, x});
ok[x] = true;
}
fill(mn, mn + n, m);
iota(dsu::dpr, dsu::dpr + n, 0);
up[0] = -1;
dfs(0);
FOR(i, 0, m) if (!ok[i]) {
auto [u, v] = E[i];
int tu = dsu::gpr(u), tv = dsu::gpr(v);
while (!is_p(tu, v)) {
assert(up[tu] != -1);
mn[up[tu]] = i;
dsu::merge(tu, pr[tu]);
tu = dsu::gpr(tu);
}
while (!is_p(tv, u)) {
assert(up[tv] != -1);
mn[up[tv]] = i;
dsu::merge(tv, pr[tv]);
tv = dsu::gpr(tv);
}
}
for (int i = m - 1; i >= 0; --i) if (ok[i])
ad[mn[i]].push_back(i);
int r = m;
for (int i = m - 1; i >= 0; --i) {
if (!ok[i]) {
W[i] = r--;
for (auto t: ad[i]) if (t > i)
W[t] = r--;
}
else if (mn[i] > i)
W[i] = r--;
}
FOR(i, 0, m)
cout << W[i] << ' ';
cout << '\n';
return 0;
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |