QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#157844 | #7106. Infinite Parenthesis Sequence | ucup-team520# | RE | 0ms | 0kb | C++14 | 4.3kb | 2023-09-02 15:55:13 | 2023-09-02 15:55:14 |
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