QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#504895 | #7610. Bus Lines | pandapythoner | WA | 61ms | 24448kb | C++23 | 5.5kb | 2024-08-04 17:04:22 | 2024-08-04 17:04:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
#define len(a) ((int)(a).size())
const ll inf = 1e18;
mt19937 rnd(234);
const int logn = 18;
const int maxn = 2e5 + 1000;
const int maxm = 2e5 + 1000;
int n, m;
vector<vector<int>> g;
pair<int, int> busses[maxm];
int bup[maxn][logn];
int sz[maxn];
int c;
int tin[maxn], tout[maxn];
int h[maxn];
int par[maxn];
int up[maxn], up_deg[maxn];
ll dp_down[maxn], dp_up[maxn];
vector<int> busses_graph[maxn];
struct tin_comp {
bool operator()(int u, int v) const { return tin[u] < tin[v]; }
};
ll sum = 0;
ll great_val[maxn];
ll great_val_sum[maxn];
int total_lca = -1;
set<int, tin_comp> st;
ll result[maxn];
int lca(int u, int v);
void clear() {
st.clear();
total_lca = -1;
sum = 0;
}
void add_vertex(int v) {
if (st.count(v)) return;
if (total_lca == -1) total_lca = v;
else total_lca = lca(total_lca, v);
auto it = st.insert(v).first;
sum += great_val_sum[v];
int a = -1;
int b = -1;
if (it != st.begin()) {
a = *prev(it);
int t = lca(a, v);
sum -= great_val_sum[t];
}
if (next(it) != st.end()) {
b = *next(it);
int t = lca(b, v);
sum -= great_val_sum[t];
}
if (a != -1 and b != -1) {
sum += great_val_sum[lca(a, b)];
}
}
ll get_sum() {
ll result = sum;
if (total_lca != -1 and total_lca != 0) {
result -= great_val_sum[par[total_lca]];
result += dp_down[total_lca];
}
return result;
}
void dfs1(int v, int p) {
par[v] = bup[v][0] = p;
for (int i = 1; i < logn; i += 1) {
bup[v][i] = bup[bup[v][i - 1]][i - 1];
}
rep(i, len(g[v])) if (g[v][i] == p) {
g[v].erase(g[v].begin() + i);
break;
}
sz[v] = 1;
int mxsz = -1;
int mxszi = -1;
rep(i, len(g[v])) {
int to = g[v][i];
dfs1(to, v);
sz[v] += sz[to];
if (mxsz < sz[to]) {
mxsz = sz[to];
mxszi = i;
}
}
if (mxszi != -1) {
swap(g[v][0], g[v][mxszi]);
}
}
void dfs2(int v, int mh = 0) {
tin[v] = c++;
h[v] = mh;
for (auto to : g[v]) {
dfs2(to, mh + 1);
}
tout[v] = c;
}
int go_up(int v, int x) {
rep(i, logn) {
if ((x >> i) & 1) {
v = bup[v][i];
}
}
return v;
}
int lca(int u, int v) {
if (h[u] < h[v]) swap(u, v);
u = go_up(u, h[u] - h[v]);
if (u == v) return u;
for (int i = logn - 1; i >= 0; i -= 1) {
if (bup[u][i] != bup[v][i]) {
u = bup[u][i];
v = bup[v][i];
}
}
assert(u != v);
return par[u];
}
void dfs3(int v) {
for (auto to : g[v]) {
dfs3(to);
if (h[up[v]] > h[up[to]]) {
up[v] = up[to];
}
}
assert(v == 0 or h[up[v]] < h[v]);
up_deg[up[v]] += 1;
dp_down[v] = up_deg[v] + 1;
for (auto to : g[v]) {
dp_down[v] += dp_down[to];
}
}
void dfs4(int v, ll sum = 0) {
sum += great_val[v];
great_val_sum[v] = sum;
for (auto to : g[v]) {
dfs4(to, sum);
}
}
void dfs6(int);
void dfs5(int v) {
for (int i = len(g[v]) - 1; i >= 0; i -= 1) {
clear();
int to = g[v][i];
dfs5(to);
}
for (int i = 1; i < len(g[v]); i += 1) {
int to = g[v][i];
dfs6(to);
}
for (auto u : busses_graph[v]) {
add_vertex(u);
}
if (g[v].empty()) add_vertex(v);
dp_up[v] = n - sz[v] + get_sum();
}
void dfs6(int v) {
for (auto u : busses_graph[v]) {
add_vertex(u);
}
if (g[v].empty()) add_vertex(v);
for (auto to : g[v]) dfs6(to);
}
void dfs7(int v) {
if (v != 0 and up[v] != 0) {
dp_up[v] += dp_up[up[v]];
}
for (auto to : g[v]) dfs7(to);
}
void solve() {
dfs1(0, 0);
c = 0;
dfs2(0);
rep(v, n) up[v] = v;
rep(v, n) up_deg[v] = 0;
rep(i, m) {
auto [u, v] = busses[i];
int t = lca(u, v);
if (h[up[u]] > h[t]) {
up[u] = t;
}
if (h[up[v]] > h[t]) {
up[v] = t;
}
}
dfs3(0);
dp_down[0] = 0;
rep(v, n) {
great_val[v] = -dp_down[v];
for (auto to : g[v]) great_val[v] += dp_down[to];
}
dfs4(0);
rep(i, n) dp_up[i] = 0;
rep(i, n) busses_graph[i] = {};
rep(i, m) {
auto [u, v] = busses[i];
busses_graph[u].push_back(v);
busses_graph[v].push_back(u);
}
clear();
dfs5(0);
dp_up[0] = 0;
dfs7(0);
rep(v, n) {
result[v] = dp_up[v];
for (auto to : g[v]) {
result[v] += dp_down[to];
}
}
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
cin >> n;
g.assign(n, vector<int>());
rep(i, n - 1) {
int u, v; cin >> u >> v; --u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
cin >> m;
rep(i, m) {
int u, v; cin >> u >> v; --u; --v;
busses[i] = make_pair(u, v);
}
solve();
rep(v, n) cout << result[v] << " ";
cout << "\n";
return 0;
}
/*
6
1 2
5 4
6 5
3 1
1 5
3
6 1
2 3
6 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 17908kb
input:
6 1 2 5 4 6 5 3 1 1 5 3 6 1 2 3 6 4
output:
6 9 9 10 7 7
result:
ok single line: '6 9 9 10 7 7 '
Test #2:
score: 0
Accepted
time: 2ms
memory: 17968kb
input:
2 1 2 1 1 2
output:
1 1
result:
ok single line: '1 1 '
Test #3:
score: -100
Wrong Answer
time: 61ms
memory: 24448kb
input:
16384 9137 490 3442 7239 1621 6904 13769 10250 14672 12572 14906 9437 6163 12339 15244 12016 3022 8670 3211 9106 11966 14817 15798 15876 6423 7394 894 7695 13877 1983 16342 15158 13574 15932 15125 10722 6989 15683 10335 8801 12301 4246 6166 3893 9347 12073 7897 12195 6510 3101 4526 15385 7017 7001 4...
output:
32747 33980 34007 34086 33923 33905 34017 42189 34041 33910 33993 34104 34004 33988 34008 34111 33998 34065 33811 50416 33991 33865 34088 33981 33975 33761 34059 34043 34288 33666 49981 34072 33791 33807 34243 34241 33996 50680 34076 34191 34084 33968 33998 34288 34104 34241 33988 34052 33962 34119 ...
result:
wrong answer 1st lines differ - expected: '34355 34048 34070 34152 33992 ...5 34333 33814 33294 34266 34337', found: '32747 33980 34007 34086 33923 ... 34256 33754 33235 34188 34265 '