This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define REP(i, n) for(int i = 0; i < n; i ++)
#define REPL(i,m, n) for(int i = m; i < n; i ++)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define SORT(arr) sort(arr.begin(), arr.end())
#define LSOne(S) ((S)&-(S))
#define M_PI 3.1415926535897932384
#define INF 999999999
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;
void dfs(int u, vvi &adj, vi &parr, vi &harr, int curh) {
harr[u] = curh;
for (auto v: adj[u]) {
if (parr[u] == v) continue;
parr[v] = u;
dfs(v, adj, parr, harr, curh+1);
}
}
int LCA(vi &parr, vi &harr, int u, int v) {
if (u==v) return u;
if (harr[u] < harr[v]) {
return LCA(parr, harr, u,parr[v]);
} else {
return LCA(parr, harr, parr[u], v);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n,e;cin>>n>>e;
vii edgearr(e);
map<ii, int> edgemap;
REP(i, e) {
int u,v;cin>>u>>v;u--;v--;
edgearr[i] = {u,v};
edgemap[{u,v}] = i;
edgemap[{v,u}] = i;
}
set<int> st;
vvi adj(n);
REP(i, n-1) {
int k;cin>>k;k--;
st.insert(k);
auto [u,v] = edgearr[k];
adj[u].push_back(v);
adj[v].push_back(u);
}
vi harr(n);
vi parr(n,-1);
dfs(0, adj,parr,harr,0);
/*REP(i, n) {
cout<<parr[i]<<" ";
}
cout<<"\n";
REP(i, n) {
cout<<harr[i]<<" ";
}cout<<"..\n";*/
vi ans(e, -1);
int curlw = 1;
REP(i, e) {
if (ans[i] != -1) continue;
if (st.find(i) != st.end()) {
ans[i] = curlw++;
continue;
}
auto [u,v] = edgearr[i];
int anc = LCA(parr, harr, u,v);
set<int> edges;
while (u!= anc) {
int pr = parr[u];
int edgeno = edgemap[{u, pr}];
if (ans[edgeno] == -1) {
edges.insert(edgeno);
}
parr[u] = anc;
u = pr;
}
while (v != anc) {
int pr = parr[v];
int edgeno = edgemap[{v, pr}];
if (ans[edgeno] == -1) {
edges.insert(edgeno);
}
parr[v] = anc;
v = pr;
}
for (auto kk: edges) {
ans[kk] = curlw++;
}
ans[i] = curlw++;
}
REP(i, e) {
cout<<ans[i]<<" ";
}
}
# | 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... |