| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1122145 | vjudge1 | Rigged Roads (NOI19_riggedroads) | C++17 | 0 ms | 0 KiB |
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;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
const int N = 3e5 + 5;
int n, m;
int head[N], pr[N], pos[N], tin[N], sz[N], index[N], res[N], s[4 * N];
bool inside[N], vis[N];
pair<int, int> dat[N];
vector<pair<int, int>> g[N];
void dfs(int u) {
sz[u] = 1;
for (auto x : g[u]) {
int v, id;
tie(v, id) = x;
g[v].erase(find(g[v].begin(), g[v].end(), make_pair(u, id)));
pr[v] = u;
index[v] = id;
dfs(v);
sz[u] += sz[v];
}
}
int order;
void hld(int u, int h) {
head[u] = h;
pos[tin[u] = ++order] = u;
if (sz[u] > 1) {
auto x = (*max_element(g[u].begin(), g[u].end(), [&](auto x, auto y) {
return sz[x.first] < sz[y.first];
})).first;
hld(x, h);
for (auto v : g[u]) {
if (v.first ^ x) {
hld(v.first, v.first);
}
}
}
}
void bld(int id = 1, int l = 1, int r = n) {
if (l == r) {
s[id] = index[pos[l]];
return;
}
int m = (l + r) / 2;
bld(id * 2, l, m);
bld(id * 2 + 1, m + 1, r);
s[id] = min(s[id * 2], s[id * 2 + 1]);
}
void upd(int i, int id = 1, int l = 1, int r = n) {
if (l == r) {
s[id] = N;
return;
}
int m = (l + r) / 2;
i <= m ? upd(i, id * 2, l, m) : upd(i, id * 2 + 1, m + 1, r);
s[id] = min(s[id * 2], s[id * 2 + 1]);
}
int qry(int u, int v, int id = 1, int l = 1, int r = n) {
if (u <= l && r <= v) {
return s[id];
}
int m = (l + r) / 2;
if (v <= m) {
return qry(u, v, id * 2, l, m);
}
if (m < u) {
return qry(u, v, id * 2 + 1, m + 1, r);
}
return min(qry(u, v, id * 2, l, m), qry(u, v, id * 2 + 1, m + 1, r));
}
int get(int u, int v) {
int res = N;
for (; head[u] ^ head[v]; u = pr[head[u]]) {
if (sz[head[u]] > sz[head[v]]) {
swap(u, v);
}
res = min(res, qry(tin[head[u]], tin[u]));
}
if (tin[u] > tin[v]) {
swap(u, v);
}
if (tin[u] + 1 <= tin[v]) {
res = min(res, qry(tin[u] + 1, tin[v]));
}
return res;
}
int ans;
void DFS(int id) {
vis[id] = 1;
int u, v;
tie(u, v) = dat[id];
if (!inside[id]) {
int nxt = N;
while ((nxt = get(u, v)) ^ N) {
DFS(nxt);
}
} else {
upd(max(tin[u], tin[v]));
}
res[id] = ++ans;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
file("A");
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
dat[i] = {u, v};
}
for (int i = 1; i < n; ++i) {
int j; cin >> j;
inside[j] = 1;
int u, v;
tie(u, v) = dat[j];
g[u].push_back({v, j});
g[v].push_back({u, j});
}
index[1] = N;
dfs(1);
hld(1, 1);
bld();
for (int i = 1; i <= m; ++i) {
if (!vis[i]) {
DFS(i);
}
cout << res[i] << " ";
}
return 0;
}