QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#392070 | #5102. Dungeon Crawler | distant_yesterday | WA | 0ms | 3548kb | C++20 | 3.3kb | 2024-04-17 05:33:54 | 2024-04-17 05:33:54 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef LOCAL
#include "cp_debug.h"
#else
#define debug(...) 42
#endif
#define int long long
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
template<typename T> void read(T &x){
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
read(first);
read(args...);
}
template<typename T> void write(T x) {
if(x > 9) write(x/10);
putchar(x%10 + '0');
}
const int N = 2030, INF = 0x3f3f3f3f3f3f3f3f;
vector<pii> G[N];
signed main() {
int n, q;
read(n, q);
ll lsum = 0;
rep(i,1,n) {
int u, v, w;
read(u, v, w);
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
lsum += w;
}
while(q--) {
int start, key, trap;
read(start, key, trap);
vi fath(n+1), depth(n+1), dist(n+1);
function<void(int,int,int,int)> dfs = [&](int u, int fa, int dep, int dis) {
fath[u] = fa;
depth[u] = dep;
dist[u] = dis;
for(auto [v, w]: G[u]) if(v != fa) {
dfs(v, u, dep+1, dis+w);
}
};
dfs(start, -1, 0, 0);
auto lca = [&](int u, int v) {
while(u != v) {
if(depth[u] > depth[v]) u = fath[u];
else if(depth[v] > depth[u]) v = fath[v];
else { u = fath[u], v = fath[v]; }
}
return u;
};
int lca_key_trap = lca(key, trap);
if(lca_key_trap == trap) {
cout<<"impossible\n";
continue;
}
debug(lca_key_trap,key,trap,lsum);
if(lca_key_trap == key) {
debug("lca = key",lca_key_trap,key,trap);
cout<<lsum*2-*max_element(dist.begin()+1, dist.end())<<'\n';
continue;
}
vi marked(n+1), is_key_parent(n+1), top(n+1);
int key_subtree = key;
is_key_parent[key] = true;
while(fath[key_subtree] != lca_key_trap) {
key_subtree = fath[key_subtree];
is_key_parent[key_subtree] = 1;
}
function<void(int,int,int)> dfs2 = [&](int u, int fa, int tp) {
marked[u] = true;
top[u] = tp;
for(auto [v, w]: G[u]) if(v != fa) {
dfs2(v, u, is_key_parent[v] ? v : tp);
}
};
debug(is_key_parent);
debug(dist,key_subtree);
dfs2(key_subtree, lca_key_trap, key_subtree);
debug(marked);
int ans = INF;
rep(i,1,n+1) {
if(marked[i]) {
debug(i,top[i],dist[i],dist[top[i]],lsum*2+dist[top[i]]-dist[lca_key_trap]-dist[i]);
ans = min(ans, lsum*2+dist[top[i]]-dist[lca_key_trap]-dist[i]);
} else {
ans = min(ans, lsum*2-dist[i]);
}
}
cout<<ans<<'\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
input:
22 5 1 2 7 2 3 5 3 4 8 3 6 6 3 7 3 2 5 6 5 8 2 8 9 11 2 10 16 1 11 12 11 12 4 11 13 9 1 14 25 14 15 4 15 16 5 15 17 6 15 18 1 15 19 8 14 20 7 20 21 9 20 22 17 1 19 9 1 9 19 1 8 9 1 9 8 2 22 11
output:
316 293 293 impossible 314
result:
ok 5 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3504kb
input:
100 100 1 2 289384 2 3 930887 2 4 692778 4 5 636916 4 6 747794 4 7 238336 4 8 885387 8 9 760493 8 10 516650 8 11 641422 8 12 202363 8 13 490028 8 14 368691 8 15 520060 8 16 897764 16 17 513927 16 18 180541 16 19 383427 16 20 89173 16 21 455737 16 22 5212 16 23 595369 16 24 702568 16 25 956430 16 26 ...
output:
103526917 103484292 106288816 104379596 104405611 104775512 104920752 105291604 103838430 104473606 104200895 104175650 105851068 104509242 103971939 105376499 105223283 104153426 105082245 104899258 104130613 104800548 106846555 104138329 103769253 104465739 104044745 104385328 105464621 105460460 ...
result:
wrong answer 7th lines differ - expected: '105434682', found: '104920752'