QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#157844#7106. Infinite Parenthesis Sequenceucup-team520#RE 0ms0kbC++144.3kb2023-09-02 15:55:132023-09-02 15:55:14

Judging History

你现在查看的是最新测评结果

  • [2023-09-02 15:55:14]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-09-02 15:55:13]
  • 提交

answer

#pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
#include<complex>
using namespace std;
typedef long long ll;
#define NUM1 1000000007LL
#define all(a) a.begin(), a.end()
#define beg(a) a.begin(), a.begin()
#define sq(a) ((a)*(a))
#define NUM2 998244353LL
#define MOD NUM2
#define fi first
#define se second
typedef double ld;
const ll MAX = ll(1e6) + 100;
const ll INF = LLONG_MAX/10;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//public free to use template by bqi343 on github
struct mi {
 	ll v; explicit operator ll() const { return v; } 
	mi():v(0) {}
	mi(ll _v):v(ll(_v%MOD)) { v += (v<0)*MOD; }
};
mi& operator+=(mi& a, mi b) { 
	if ((a.v += b.v) >= MOD) a.v -= MOD; 
	return a; }
mi& operator-=(mi& a, mi b) { 
	if ((a.v -= b.v) < 0) a.v += MOD; 
	return a; }
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator*(mi a, mi b) { return mi((ll)a.v*b.v); }
mi& operator*=(mi& a, mi b) { return a = a*b; }
mi pow(mi a, ll p) { assert(p >= 0); // won't work for negative p
	return p==0?1:pow(a*a,p/2)*(p&1?a:1); }
mi inv(mi a) { assert(a.v != 0); return pow(a,MOD-2); }
mi operator/(mi a, mi b) { return a*inv(b); }
bool operator==(mi a, mi b) { return a.v == b.v; }
bool operator==(mi a, ll b){ return a.v == b;}
ostream& operator<<(ostream& os, const mi& val)
{
    os << (ll) val;
    return os;
} 
ld epsilon =1e-12;
typedef complex<ld> pt;
#define x real()
#define y imag()
ld dot(pt a, pt b){
  return (conj(a)*b).x;
}
ld cross(pt a, pt b){
  return (conj(a)*b).y;
}
//Lazy Segment Tree supporting range assignment, range addition and range query


vector<vector<pair<ll,ll>>> adj;
const ll logn=21;
const ll maxn=1e5+100;
ll par[maxn][logn];
ll par_val[maxn][logn];
vector<bool> red; 
ll C[maxn];
ll tin[maxn],tout[maxn];
ll timer=0;
void dfs(ll v, ll p, ll cost,ll last){
  tin[v]=timer++;
  par[v][0]=p;
  par_val[v][0]=last;
  for(ll i=1;i<logn;i++){
    par[v][i]=par[par[v][i-1]][i-1];
  }
  for(ll i=1;i<logn;i++){
    par_val[v][i]=par_val[v][i-1]+par_val[par[v][i-1]][i-1];
  }
  if(red[v])cost=0;
  C[v]=cost;
  for(auto e: adj[v]){
    if(e.first==p)continue;
     dfs(e.first,v,cost+e.second,e.second);
  }
  tout[v]=timer++;
}
bool anc(ll u, ll v){
  return (tin[u]<=tin[v] and tout[u]>=tout[v]);
}
ll lca(ll u, ll v){
  if(anc(u,v))return u;
  if(anc(v,u))return v;
  for(ll i=logn-1;i>=0;i--){
    if(!anc(par[u][i],v))u=par[u][i];
  }
  return par[u][0];
}
ll diffCost(ll u, ll v){
  assert(anc(u,v));
  if(u==v)return 0;
  ll ans=0;
  for(ll i=logn-1;i>=0;i--){
    if(!anc(par[v][i],u)){ans+=par_val[v][i];v=par[v][i];}
  }
  return ans+par_val[v][0];
}
ll check(ll u, ll r){
  assert(anc(r, u));
  return min(C[u],diffCost(r,u));
}
void solve(){
  timer=0;
  ll n,m,q;cin>>n>>m>>q;
  red.assign(n+1,0);
  for(ll i=0;i<m;i++){
    ll u;cin>>u;u--;
    red[u]=true;
  }
  adj.assign(n,vector<pair<ll,ll>>());
  for(ll i  =0;i<n-1;i++){
    ll u,v;ll w;cin>>u>>v>>w;u--;v--;
    adj[u].push_back({v,w});
    adj[v].push_back({u,w});
  }
  dfs(0,0,0,0);
  while(q--){
    ll k;cin>>k;
    vector<pair<ll,ll>> b;
    for(ll i=0;i<k;i++){
      ll u;cin>>u;u--;
      b.push_back({C[u],u});
    }
    sort(b.begin(),b.end());
    reverse(b.begin(),b.end());
    vector<ll> a;

    for(auto e: b)a.push_back(e.second);
    // for(auto  e:a)cout<<e<<" ";cout<<endl;
    // for(auto  e:b)cout<<e.first<<" ";cout<<endl;
    ll curr=C[a[0]];
    ll sol=curr;
    if(k==1){
      cout<<0<<"\n";
      continue;
    }
    sol=min(sol,C[a[1]]);
    curr=0;
    ll last=a[0];
    // for(int i=0;i<n;i++){
    //   for(auto e: par_val[i]){
    //     cout<<e<<" ";
    //   }
    //   cout<<endl;
    // }
    for(ll i=1;i<k;i++){
      ll p=lca(last,a[i]);
      // cout<<i<<endl;
      // cout<<p<<endl;
      if(p==last){
        curr=max(curr,check(a[i],p));
        sol=min(sol,max(curr,((i==k-1)?0ll:C[a[i+1]])));
      }
      else{
        curr=curr+diffCost(p,last);
        curr=max(curr,check(a[i],p));
        sol=min(sol,max(curr,((i==k-1)?0ll:C[a[i+1]])));
      }
      last=p;
    }
    cout<<sol<<"\n";
  }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t = 1;
    cin >> t;
    // ll  tt=1;
    // vector<ll> a(1e5+11,0);
    // seg.build(a);
    while(t--)
    {
        solve();}
    return 0;   
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

3
(())
3
0 -3 2
1 -2 3
2 0 0
))()(
3
0 -3 4
2 1 3
3 -4 -1
))()(()(
4
1234 -5678 9012
123 -456 789
12 -34 56
1 -2 3

output:


result: