QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#128889 | #6736. Alice and Bob | ckiseki# | WA | 1ms | 12832kb | C++20 | 2.7kb | 2023-07-21 16:44:36 | 2023-07-21 16:45:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int cnt = sizeof...(T);
(..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
cerr << "\e[1;32m[ " << s << " ] = [";
while (L != R) cerr << " " << *L++;
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
namespace {
int lowbit(int x) { return x & (-x); }
constexpr int kN = 100000 + 5;
constexpr int kLog = 20;
vector<int> g[kN];
int tin[kN], tout[kN], tc;
int pa[kN][kLog];
int chain[kN], chains;
int head[kN];
void dfs(int u, int f) {
pa[u][0] = f;
for (int i = 1; i < kN; ++i)
pa[u][i] = pa[pa[u][i - 1]][i - 1];
tin[u] = tc++;
for (int v : g[u]) {
if (v == f)
continue;
dfs(v, u);
if (lowbit(chain[u]) < lowbit(chain[v]))
chain[u] = chain[v];
}
if (chain[u] == 0)
chain[u] = ++chains;
tout[u] = tc;
head[chain[u]] = u;
}
bool anc(int u, int v) {
return tin[u] <= tin[v] and tout[v] <= tout[u];
}
int lca(int u, int v) {
if (anc(u, v)) return v;
for (int i = kLog - 1; i >= 0; --i) {
if (not anc(pa[u][i], v))
u = pa[u][i];
}
return pa[u][0];
}
vector<tuple<int, int, int>> path[kN];
int64_t dp[kN][13];
void solve(int u) {
for (int v : g[u]) {
solve(v);
}
if (g[u].empty())
return;
}
} // namespace
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
u -= 1, v -= 1;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(0, 0);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
u -= 1, v -= 1;
path[lca(u, v)].emplace_back(u, v, w);
}
for (int i = 0; i < n; ++i) {
int fi = -1;
vector<int> cur;
for (int j : g[i]) {
if (j != pa[i][0]) {
if (chain[j] == chain[i])
fi = j;
else
cur.push_back(j);
}
}
if (fi != -1) {
cur.push_back(fi);
reverse(cur.begin(), cur.end());
}
g[i] = cur;
}
solve(0);
int64_t ans = 0;
for (auto r : dp[0])
ans = max(ans, r);
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 12832kb
input:
1
output:
0
result:
wrong answer 1st numbers differ - expected: '1', found: '0'