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> //Logm
using namespace std;
#define int long long
#define II pair<int,int>
#define fi first
#define se second
const int N = 3e5+5;
int n, m;
II e[N];
int idx[N];
bool spec[N];
int par[N], rak[N];
void init(int n) {
for (int i = 1; i <= n; ++i) {
par[i] = i;
rak[i] = 0;
}
}
int find(int u) {
if (par[u] != u) par[u] = find(par[u]);
return par[u];
}
bool join(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return 0;
if (rak[u] == rak[v]) ++rak[u];
if (rak[u] < rak[v]) par[u] = v;
else par[v] = u;
return 1;
}
namespace sub1 {
void solve() {
int p[m];
for (int i = 0; i < m; ++i) p[i] = i + 1;
vector<int> ans;
do {
init(n);
bool flag = 0;
for (int i = 0; i < m; ++i) {
if (spec[p[i]]) {
if (!join(e[p[i]].fi, e[p[i]].se)) {
flag = 1;
break;
}
} else {
if (join(e[p[i]].fi, e[p[i]].se)) {
flag = 1;
break;
}
}
}
if (flag) continue;
vector<int> res(m);
for (int i = 0; i < m; ++i)
res[p[i] - 1] = i + 1;
if (ans.empty()) ans = res;
else ans = min(ans, res);
} while (next_permutation(p, p + m));
for (int i: ans) cout << i << ' ';
exit(0);
}
}
namespace sub2 {
vector<II> adj[N];
int ans[N];
int index;
II par[N];
int dep[N];
void build(int u) {
for (II ed: adj[u]) {
int v = ed.fi, id = ed.se;
if (v != par[u].fi) {
par[v] = II(u, id);
dep[v] = dep[u] + 1;
build(v);
}
}
}
void getpath(int u, int v, vector<int> &path) {
if (dep[u] < dep[v]) swap(u, v);
while (dep[u] > dep[v]) {
path.push_back(par[u].se);
u = par[u].fi;
}
if (u == v) return;
while (u != v) {
path.push_back(par[u].se);
u = par[u].fi;
path.push_back(par[v].se);
v = par[v].fi;
}
}
void solve() {
for (int i = 1; i < n; ++i) {
int u = e[idx[i]].fi, v = e[idx[i]].se;
adj[u].push_back(II(v, idx[i]));
adj[v].push_back(II(u, idx[i]));
}
build(1);
for (int i = 1; i <= m; ++i) {
if (spec[i]) {
if (ans[i] == 0) ans[i] = ++index;
} else {
int u = e[i].fi, v = e[i].se;
// đường đi từ u đến v trên cây khung phải được đánh số nhỏ hơn
vector<int> path;
getpath(u, v, path);
sort(path.begin(), path.end());
for (int x: path) {
if (ans[x] == 0) ans[x] = ++index;
}
ans[i] = ++index;
}
}
for (int i = 1; i <= m; ++i)
cout << ans[i] << ' ';
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen("ZONING.inp", "r")) {
freopen("ZONING.inp", "r", stdin);
freopen("ZONING.out", "w", stdout);
}
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
e[i] = II(u, v);
}
for (int i = 1; i < n; ++i) {
cin >> idx[i];
spec[idx[i]] = 1;
}
if (m <= 9) sub1::solve();
sub2::solve();
return 0;
}
Compilation message (stderr)
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
141 | freopen("ZONING.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | freopen("ZONING.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... |