QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#504862 | #7610. Bus Lines | pandapythoner | WA | 67ms | 28688kb | C++23 | 5.4kb | 2024-08-04 16:49:00 | 2024-08-04 16:49:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#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];
if (it != st.begin()) {
int u = *prev(it);
int t = lca(u, v);
sum -= great_val_sum[t];
}
if (next(it) != st.end()) {
int u = *next(it);
int t = lca(u, v);
sum -= great_val_sum[t];
}
}
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);
}
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);
}
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];
}
}
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: 24100kb
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: 0ms
memory: 26076kb
input:
2 1 2 1 1 2
output:
1 1
result:
ok single line: '1 1 '
Test #3:
score: -100
Wrong Answer
time: 67ms
memory: 28688kb
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 -287821865 -281402325 -281348504 -287847358 -289794241 -281420229 -365404712 -281384377 -287954327 -287742505 -281348486 -287847446 -289043037 -281384410 -281348479 -287837060 -281348525 -289192412 -281367833 -288953757 -281634652 -281348502 -287760431 -281402357 -288123725 -287750130 -2891905...
result:
wrong answer 1st lines differ - expected: '34355 34048 34070 34152 33992 ...5 34333 33814 33294 34266 34337', found: '32747 -287821865 -281402325 -2...91542479 -287742310 -281348325 '