QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#158319 | #7103. Red Black Tree | ucup-team1134# | AC ✓ | 1753ms | 43168kb | C++17 | 6.3kb | 2023-09-02 16:25:22 | 2023-09-02 16:25:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=100005,INF=1<<30;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// https://beet-aizu.github.io/library/tree/auxiliarytree.cpp.html
//BEGIN CUT HERE
struct LowestCommonAncestor{
int h;
vector< vector<int> > G,par;
vector<int> dep;
LowestCommonAncestor(int n):G(n),dep(n){
h=1;
while((1<<h)<=n) h++;
par.assign(h,vector<int>(n,-1));
}
void add_edge(int u,int v){
G[u].emplace_back(v);
G[v].emplace_back(u);
}
void dfs(int v,int p,int d){
par[0][v]=p;
dep[v]=d;
for(int u:G[v])
if(u!=p) dfs(u,v,d+1);
}
void build(int r=0){
int n=G.size();
dfs(r,-1,0);
for(int k=0;k+1<h;k++)
for(int v=0;v<n;v++)
if(~par[k][v])
par[k+1][v]=par[k][par[k][v]];
}
int lca(int u,int v){
if(dep[u]>dep[v]) swap(u,v);
for(int k=0;k<h;k++)
if((dep[v]-dep[u])>>k&1)
v=par[k][v];
if(u==v) return u;
for(int k=h-1;k>=0;k--)
if(par[k][u]!=par[k][v])
u=par[k][u],v=par[k][v];
return par[0][u];
}
int distance(int u,int v){
return dep[u]+dep[v]-dep[lca(u,v)]*2;
}
};
//BEGIN CUT HERE
struct AuxiliaryTree : LowestCommonAncestor{
using super = LowestCommonAncestor;
vector<int> idx;
vector<vector<int>> T;
AuxiliaryTree(int n):super(n),idx(n),T(n){}
void dfs(int v,int p,int &pos){
idx[v]=pos++;
for(int u:G[v])
if(u!=p) dfs(u,v,pos);
}
void build(int r=0){
super::build(r);
int pos=0;
dfs(r,-1,pos);
}
void add_aux_edge(int u,int v){
T[u].emplace_back(v);
T[v].emplace_back(u);
}
using super::lca, super::dep;
void query(vector<int> &vs){
assert(!vs.empty());
sort(vs.begin(),vs.end(),
[&](int a,int b){return idx[a]<idx[b];});
vs.erase(unique(vs.begin(),vs.end()),vs.end());
int k=vs.size();
stack<int> st;
st.emplace(vs[0]);
for(int i=0;i+1<k;i++){
int w=lca(vs[i],vs[i+1]);
if(w!=vs[i]){
int l=st.top();st.pop();
while(!st.empty() and dep[w]<dep[st.top()]){
add_aux_edge(st.top(),l);
l=st.top();st.pop();
}
if(st.empty() or st.top()!=w){
st.emplace(w);
vs.emplace_back(w);
}
add_aux_edge(w,l);
}
st.emplace(vs[i+1]);
}
while(st.size()>1){
int c=st.top();st.pop();
add_aux_edge(st.top(),c);
}
}
void clear(const vector<int> &ws){
for(int w:ws) T[w].clear();
}
};
vector<pair<int,ll>> G[MAX];
ll dis[MAX],D[MAX];
void make(int u,int p){
for(auto [to,co]:G[u]){
if(to==p) continue;
if(dis[to]==0){
}else{
dis[to]=dis[u]+co;
}
D[to]=D[u]+co;
make(to,u);
}
}
int par[MAX];
void mk(int u,int p,AuxiliaryTree &T){
par[u]=p;
for(int to:T.T[u]){
if(to==p) continue;
mk(to,u,T);
}
}
bool seen[MAX],imp[MAX];
void DFS(int u,int p,int x,ll &ma,AuxiliaryTree &T,multiset<ll> &SE){
if(seen[u]) return;
seen[u]=true;
if(imp[u]){
if(D[u]-D[x]==dis[u]-dis[x]){
SE.erase(SE.find(dis[u]));
chmax(ma,D[u]);
}
}
for(int to:T.T[u]){
if(to==par[u]) continue;
DFS(to,u,x,ma,T,SE);
}
}
ll solve(vector<int> st,vector<int> use,AuxiliaryTree &T){
vector<pair<ll,int>> di;
for(int i=0;i<si(use);i++){
di.push_back(mp(dis[use[i]],use[i]));
}
sort(all(di));
if(di.back().fi==0) return 0LL;
for(int x:use) imp[x]=true;
int v=di.back().se;
multiset<ll> SE;
ll ma=0;
for(auto [d,x]:di) SE.insert(d);
ll ans=(*SE.rbegin());
int ro=st[0];
for(int x:st){
if(T.idx[ro]>T.idx[x]) ro=x;
}
mk(ro,-1,T);
while(v!=-1){
DFS(v,-1,v,ma,T,SE);
ll re=-1;
if(si(SE)) chmax(re,(*SE.rbegin()));
chmax(re,ma-D[v]);
chmin(ans,re);
int p=par[v];
if(p==-1||D[v]-D[p]!=dis[v]-dis[p]){
break;
}else{
v=par[v];
}
}
for(int x:use) imp[x]=false;
for(int x:st) seen[x]=false;
return ans;
}
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
int QQ;cin>>QQ;
while(QQ--){
int N,M,Q;cin>>N>>M>>Q;
for(int i=0;i<N;i++){
G[i].clear();
dis[i]=1LL<<60;
D[i]=1LL<<60;
}
D[0]=0;
for(int i=0;i<M;i++){
int x;cin>>x;x--;
dis[x]=0;
}
AuxiliaryTree T(N);
for(int i=0;i<N-1;i++){
int a,b;cin>>a>>b;a--;b--;
ll c;cin>>c;
T.add_edge(a,b);
G[a].push_back(mp(b,c));
G[b].push_back(mp(a,c));
}
T.build();
make(0,-1);
while(Q--){
int K;cin>>K;
vector<int> st(K),use;
for(int i=0;i<K;i++){
int x;cin>>x;x--;
st[i]=x;
}
use=st;
T.query(st);
cout<<solve(st,use,T)<<"\n";
T.clear(st);
}
}
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8144kb
input:
2 12 2 4 1 9 1 2 1 2 3 4 3 4 3 3 5 2 2 6 2 6 7 1 6 8 2 2 9 5 9 10 2 9 11 3 1 12 10 3 3 7 8 4 4 5 7 8 4 7 8 10 11 3 4 5 12 3 2 3 1 2 1 2 1 1 3 1 1 1 2 1 2 3 1 2 3
output:
4 5 3 8 0 0 0
result:
ok 7 lines
Test #2:
score: 0
Accepted
time: 1753ms
memory: 43168kb
input:
522 26 1 3 1 1 4 276455 18 6 49344056 18 25 58172365 19 9 12014251 2 1 15079181 17 1 50011746 8 9 2413085 23 24 23767115 22 2 26151339 26 21 50183935 17 14 16892041 9 26 53389093 1 20 62299200 24 18 56114328 11 2 50160143 6 26 14430542 16 7 32574577 3 16 59227555 3 15 8795685 4 12 5801074 5 20 57457...
output:
148616264 148616264 0 319801028 319801028 255904892 317070839 1265145897 1265145897 1072765445 667742619 455103436 285643094 285643094 285643094 317919339 0 785245841 691421476 605409472 479058444 371688030 303203698 493383271 919185207 910180170 919185207 121535083 181713164 181713164 181713164 181...
result:
ok 577632 lines
Extra Test:
score: 0
Extra Test Passed