| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1119539 | vjudge1 | Min-max tree (BOI18_minmaxtree) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
using ll = long long;
using pii = pair <int, int>;
const int N = 2e5 + 5, inf = 1e9;
int n, sz[N], d[N], ind[N], par[N], ct, tp[N], l[N], r[N], node[N];
vector <int> g[N], gg[N], add[N][2], del[N][2];
char C[N];
int U[N], V[N], Z[N], used[N], timer, Mt[N];
void calc(int v, int p = 0) {
sz[v] = 1;
par[v] = p;
for (auto to : g[v]) {
if (to != p) {
d[to] = d[v] + 1;
calc(to, v);
sz[v] += sz[to];
}
}
}
void dfs(int v, int p = 0, int top = 1) {
ind[v] = ++ct;
node[ind[v]] = v;
tp[v] = top;
int mx = 0, bg = -1;
for (auto to : g[v]) {
if (to != p && mx < sz[to])
mx = sz[to], bg = to;
}
if (bg != -1)
dfs(bg, v, top);
for (auto to : g[v]) {
if (to != p && to != bg)
dfs(to, v, to);
}
}
bool kuhn(int v) {
if (used[v] == timer)
return 0;
used[v] = timer;
for (auto to : gg[v]) {
if (Mt[to] != -1) {
Mt[to] = v;
return 1;
}
}
for (auto to : gg[v]) {
if (kuhn(Mt[to])) {
Mt[to] = v;
return 1;
}
}
return 0;
}
int main() {
ios :: sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
calc(1);
dfs(1);
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
char c;
int u, v, z;
cin >> c >> u >> v >> z;
C[i] = c;
U[i] = u;
V[i] = v;
Z[i] = z;
int mn = inf;
vector <pii> seg;
while (tp[u] != tp[v]) {
if (d[tp[u]] < d[tp[v]]) swap(u, v);
seg.pb({ind[tp[u]], ind[u]});
mn = min(mn, seg.back().f);
u = par[tp[u]];
}
if (d[u] > d[v]) swap(u, v);
seg.pb({ind[u], ind[v]});
mn = min(mn, seg.back().f);
for (auto [l, r] : seg) {
if (l == mn)
++l;
add[l][(c == 'm')].pb(z);
del[r + 1][(c == 'm')].pb(z);
}
}
multiset <int> mt[2];
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 2; ++j) {
for (auto z : add[i][j])
mt[j].insert(z);
for (auto z : del[i][j])
mt[j].erase(mt[j].find(z));
}
r[i] = inf;
if (sz(mt[0]))
r[i] = *mt[0].begin();
if (sz(mt[1]))
l[i] = *mt[1].rbegin();
}
if (n > 1000) {
for (int i = 1; i <= n; ++i) {
if (par[i])
cout << i << ' ' << par[i] << ' ' << r[ind[i]] << '\n';
}
return 0;
}
for (int i = 0; i < q; ++i) {
char c;
int u, v, z;
c = C[i];
u = U[i];
v = V[i];
z = Z[i];
int mn = inf;
vector <pii> seg;
while (tp[u] != tp[v]) {
if (d[tp[u]] < d[tp[v]]) swap(u, v);
seg.pb({ind[tp[u]], ind[u]});
mn = min(mn, seg.back().f);
u = par[tp[u]];
}
if (d[u] > d[v]) swap(u, v);
seg.pb({ind[u], ind[v]});
mn = min(mn, seg.back().f);
for (auto [x, y] : seg) {
if (x == mn)
++x;
for (int j = x; j <= y; ++j) {
if (c == 'm' && l[j] == z) {
gg[i].pb(j + q);
cout << i << ' ' << j + q << '\n';
}
if (c == 'M' && r[j] == z) {
cout << i << ' ' << j + q << '\n';
gg[i].pb(j + q);
}
}
}
}
for (int i = 1; i <= n; ++i)
Mt[i] = -1;
for (int i = 0; i < q; ++i) {
++timer;
kuhn(i);
}
set <int> st;
for (int i = 1; i <= n; ++i)
st.insert(mt[i + q]);
assert(sz(st) == q);
for (int i = 1; i <= n; ++i) {
if (!par[i])
continue;
if (Mt[ind[i] + q] == -1)
cout << i << ' ' << par[i] << ' ' << l[ind[i]] << '\n';
else
cout << i << ' ' << par[i] << ' ' << Z[Mt[ind[i] + q]] << '\n';
}
return 0;
}