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>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "zoning"
template<class T> bool minimize(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool maximize(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
void setIO() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(file".inp", "r")) {
freopen(file".inp", "r", stdin);
freopen(file".out", "w", stdout);
}
}
const int N = 3e5+5, LOG = 19;
int n, m, cur, id[N], par[N][LOG], high[N], up_w[N];
vector<ii> edges(1);
vector<ii> adj[N];
bool spec[N];
struct dsu {
int anc[N], up[N];
void reset() {
foru(i, 1, max(n, m)) {
anc[i] = -1;
up[i] = i;
}
}
int root(int u) {
return anc[u] < 0 ? u : anc[u] = root(anc[u]);
}
void join(int u, int v) {
if ((u = root(u)) == (v = root(v))) return;
if (anc[u] > anc[v]) swap(u, v);
anc[u] += anc[v];
if (high[up[u]] > high[up[v]]) up[u] = up[v];
anc[v] = u;
}
} comp, proc;
void dfs_first(int u, int p) {
foru(i, 1, LOG-1) {
par[u][i] = par[par[u][i-1]][i-1];
}
fore(x, adj[u]) {
int v = x.fi, t = x.se;
if (v == p) continue;
up_w[v] = t;
high[v] = high[u] + 1;
par[v][0] = u;
dfs_first(v, u);
}
}
int lca(int u, int v) {
if (high[u] < high[v]) swap(u, v);
ford(i, LOG-1, 0) if (high[par[u][i]] >= high[v]) u = par[u][i];
if (u == v) return u;
ford(i, LOG-1, 0) if (par[u][i] != par[v][i]) {
u = par[u][i];
v = par[v][i];
}
return par[u][0];
}
int main() {
setIO();
cin >> n >> m;
foru(i, 1, m) {
int u, v;
cin >> u >> v;
edges.emplace_back(u, v);
}
foru(i, 1, n-1) {
int e; cin >> e;
spec[e] = 1;
int u = edges[e].fi, v = edges[e].se;
adj[u].emplace_back(v, e);
adj[v].emplace_back(u, e);
}
high[0] = -1;
dfs_first(1, 0);
comp.reset();
proc.reset();
foru(i, 1, m) {
if (id[i]) continue;
int u = edges[i].fi, v = edges[i].se;
if (!spec[i] && comp.root(u) != comp.root(v)) {
int l = lca(u, v);
vector<int> tmp;
u = proc.up[proc.root(u)];
v = proc.up[proc.root(v)];
while (high[u] > high[l]) {
tmp.push_back(up_w[u]);
proc.join(u, par[u][0]);
u = proc.up[proc.root(u)];
}
while (high[v] > high[l]) {
tmp.push_back(up_w[v]);
proc.join(v, par[v][0]);
v = proc.up[proc.root(v)];
}
sort(all(tmp));
fore(x, tmp) {
id[x] = ++cur;
}
}
id[i] = ++cur;
}
foru(i, 1, m) cout << id[i] << " ";
}
Compilation message (stderr)
riggedroads.cpp: In function 'void setIO()':
riggedroads.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | freopen(file".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | freopen(file".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |