QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#175470 | #7103. Red Black Tree | _Sheepsheep | WA | 1345ms | 99096kb | C++14 | 2.3kb | 2023-09-10 18:23:09 | 2023-09-10 18:23:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define double long double
const ll N = 2e6+9 ;
const ll INF = 1e18 ;
ll gcd( ll a , ll b ){ return a == 0 ? b : gcd(b%a,a) ; }
int n , m , q ;
vector<pair<int,ll>>g[ N ] ;
ll cost[ N ] , deep[ N ] , f[ N ][ 30 ] , dis[ N ] ;
bool cmp( int a , int b ){
return cost[ a ] > cost[ b ] ;
}
void dfs( ll x , ll fa ){
f[ x ][ 0 ] = fa ;
for( auto u : g[x] ){
if( u.first == fa ) continue ;
cost[ u.first ] = min( cost[u.first] , cost[ x ] + u.second ) ;
deep[ u.first ] = deep[ x ] + u.second ;
dis[ u.first ] = dis[ x ] + 1 ;
dfs( u.first , x ) ;
}
for( int i = 1 ; i <= 25 ; i ++ ) f[ x ][ i ] = f[ f[x][i-1] ][i-1] ;
}
int LCA( int x , int y ){
if( x == y ) return x ;
if( dis[ x ] < dis[ y ] ) swap( x , y ) ;
for( int i = 25 ; i >= 0 ; i -- ) if( dis[ f[x][i] ] >= dis[ y ] ){
x = f[x][i] ;
}
if( x == y ) return x ;
for( int i = 25 ; i >= 0 ; i -- ) if( f[x][i] != f[y][i] ){
x = f[x][i] ; y = f[y][i] ;
}
return f[x][0] ;
}
void solve(){
cin >> n >> m >> q ; //点,红色点数,询问次数
for( int i = 1 ; i <= n ; i ++ ){
g[i].clear() ;
deep[ i ] = dis[i] = 0 ; cost[ i ] = INF ;
}
for( int i = 1 , x ; i <= m ; i ++ ){
cin >> x ; cost[ x ] = 0 ;
}
for( int i = 1 ; i < n ; i ++ ){
ll x , y , w ; cin >> x >> y >> w ;
g[ x ].push_back( {y,w} ) ;
g[ y ].push_back( {x,w} ) ;
}
dfs( 1 , 0 ) ;
while( q-- ){
ll k ; cin >> k ;
vector<ll>v(k+1) ;
for( int i = 1 ; i <= k ; i ++ ) cin >> v[ i ] ;
sort( v.begin()+1 , v.end() , cmp ) ;
ll lca = v[1] , ans = cost[ v[1] ] , maxdeep = deep[ v[1] ] ;
for( int i = 1 ; i <= k ; i ++ ){
lca = LCA(lca,v[i]) ;
maxdeep = max( maxdeep , deep[i] ) ;
ll res = max( ((i!=k)?cost[ v[i+1] ]:0) , maxdeep-deep[lca] ) ;
ans = min( ans , res ) ;
}
cout << ans << "\n" ;
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
ll tt = 1 ; cin >> tt ;
while( tt-- ) solve() ;
return 0 ;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 57664kb
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: -100
Wrong Answer
time: 1345ms
memory: 99096kb
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 307718947 493383271 919185207 910180170 919185207 52784081 181713164 181713164 181713164 1817...
result:
wrong answer 23rd lines differ - expected: '303203698', found: '307718947'