QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#87960 | #5102. Dungeon Crawler | zoker | WA | 2ms | 3588kb | C++17 | 4.3kb | 2023-03-14 21:52:54 | 2023-03-14 21:53:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt")
using ll = long long int;
using ull = unsigned long long int;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using vii = vector<ii>;
using ld = long double;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree < T, null_type, less<T>,
rb_tree_tag,
tree_order_statistics_node_update >;
#ifdef SA_DEBUG
template <class T>
void print(T a) {cerr << a << endl;}
template <class T, class... V>
void print(T a, V... b) {cerr << a << ", "; print(b...);}
#define dbg(...) cerr << "[" << __LINE__ << "] " << #__VA_ARGS__ << " :: ", print(__VA_ARGS__)
#else
#define dbg(...) 7
#endif
#define eb emplace_back
#define fi first
#define se second
const ll INFL = 2e18;
const int INF = 1e9;
const double PI = acos(-1);
const ll mod = 1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T, class V>
ostream& operator << (ostream &s, pair<T, V> a){
s << a.fi << ' ' << a.se; return s;
}
template<class T, class V>
istream& operator >> (istream &s, pair<T, V> &a){
s >> a.fi >> a.se; return s;
}
template<class T>
ostream& operator << (ostream &s, vector<T> a){
for(int i = 0; i < (int)a.size(); i++){
if(i > 0)s << ' ' ;
s << a[i];
} return s;
}
template<class T>
istream& operator >> (istream &s, vector<T> &a){
for(T &x : a)s >> x;
return s;
}
template<class T>
void input(T a[], int l, int r, istream &s = cin){
while(l <= r)s >> a[l++];
}
template<class T>
void output(T a[], int l, int r, bool en = true, ostream &s = cout){
while(l <= r){ s << a[l++];
if(l <= r) s << ' ';
} if(en)s << "\n";
}
const int N = 2e3+3, K = 13, M = 2e5 + 5;
//====================================================================//
ll dis[N];
ll D[N];
int up[N][K];
ll ans[M];
vector<ii> adj[N];
int tin[N], tout[N];
map<int, vector<ii>> khuja[N];
int T;
void dfs(int ind, int par, ll d){
up[ind][0] = par;
for(int i = 1; i < K; i++){
up[ind][i] = up[up[ind][i - 1]][i - 1];
}
tin[ind] = T++;
dis[ind] = d;
D[ind] = d;
for(auto [x, w] : adj[ind]){
if(x == par)continue;
dfs(x, ind, d + w);
dis[ind] = max(dis[ind], dis[x]);
}
tout[ind] = T++;
}
#define isanc(u,v) (tin[u] <= tin[v] && tout[u] >= tout[v])
ii LCA(int u, int v){
if(isanc(u, v))return {u, u};
for(int i = K - 1; i >= 0; i--){
if(!isanc(up[u][i], v))u = up[u][i];
}
return {up[u][0], u};
}
ll fetch(int ind, int par, ll val){
ii mx1 = {-1, -1};
ii mx2 = {-1, -1};
for(auto [x, y] : adj[ind]){
if(x == par)continue;
if(mx1.fi < dis[x]){
mx2 = mx1;
mx1 = {dis[x], x};
}else if(mx2.fi < dis[x]){
mx2 = {dis[x], x};
}
}
for(auto [x, y] : adj[ind]){
if(x == par)continue;
ll temp = val;
if(mx1.se != x)temp = max(temp, mx1.fi);
if(mx2.se != x)temp = max(temp, mx2.fi);
ll gt = fetch(x, ind, temp);
for(auto [z, s] : khuja[ind][x]){
ans[z] = max(temp, gt + 2 * D[ind]);
}
}
khuja[ind].clear();
return dis[ind] - 2 * D[ind];
}
void testcase(){
int n, q;
cin >> n >> q;
ll tot = 0;
for(int i = 1; i < n; i++){
int x, y, z;
cin >> x >> y >> z;
adj[x].eb(y, z);
adj[y].eb(x, z);
tot += 2 * z;
}
vector<vector<tuple<int, int, int>>> qr(n + 1);
for(int i = 0; i < q; i++){
int s, k, t;
cin >> s >> k >> t;
qr[s].eb(k, t, i);
}
for(int i = 1; i <= n; i++){
if(qr[i].empty())continue;
T = 0;
dfs(i, i, 0);
for(auto [k, t, idx] : qr[i]){
auto [l, l2] = LCA(k, t);
if(l == k){
ans[idx] = dis[i];
continue;
}
if(l == t){
ans[idx] = -1;
continue;
}
assert(isanc(l, l2));
assert(isanc(l2, k));
assert(isanc(l, t));
assert(!isanc(l2, t));
khuja[l][l2].eb(idx, k);
}
fetch(i, i, -1);
}
for(int i = 0; i < q; i++){
if(ans[i] == -1)cout << "impossible\n";
else {
cout << tot - ans[i] << "\n";
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int TT = 1;
//cin >> T;
for(int qq = 1; qq <= TT; ++qq){
//cout << "Case #" << qq << ": ";
testcase();
}
return 0;
}
/*
6 1597352862016328480
*/
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3424kb
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: 3588kb
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 105633958 104379596 104405611 104775512 105434682 105291604 103838430 105371370 104677980 104175650 105887913 104509242 103971939 105376499 105223283 104153426 105082245 105413188 104130613 104800548 104952840 104138329 103769253 104428894 104044745 104385328 104530012 105460460 ...
result:
wrong answer 3rd lines differ - expected: '106288816', found: '105633958'