제출 #236197

#제출 시각아이디문제언어결과실행 시간메모리
236197infinite_iqValley (BOI19_valley)C++14
0 / 100
183 ms25336 KiB
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #include <bits/stdc++.h> using namespace std; #define sqr 400 #define mp make_pair #define mid (l+r)/2 #define Le Node * 2 #define Ri Node * 2 + 1 #define pb push_back #define ppb pop_back #define fi first #define se second #define lb lower_bound #define ub upper_bound #define ins insert #define era erase #define C continue #define mem(dp,i) memset(dp,i,sizeof(dp)) #define mset multiset #define all(x) x.begin(), x.end() #define gc getchar_unlocked typedef long long ll; typedef short int si; typedef long double ld; typedef pair<int,int> pi; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll; typedef pair<double,ll>pdi; const ll inf=1e18; const ll Mod=1e9+7; const ld pai=acos(-1); int n , m , q , Root ; pi E [100009] ; vpi v [100009] ; int Dis [100009] , w [100009] , Dp [100009][20] , Mn [100009][20] , Best [100009] , Yes [100009] ; void Fill ( int Node , int p , int Sum ) { Dp [Node][0] = p ; w [Node] = w [p] + 1 ; Dis[Node] = Sum ; Best [Node] = ( Yes [Node] ? Dis [Node] : 1e9 ) ; for ( auto u : v [Node] ) { if ( u.fi == p ) C ; Fill ( u.fi , Node , Sum + u.se ) ; Best [Node] = min ( Best [Node] , Best [u.fi] ) ; } } int Check ( int a , int b ) { if ( w [a] < w [b] ) swap ( a , b ) ; int l = w [a] - w [b] ; for ( int i = 0 ; i < 20 ; i ++ ) { if ( ( l & ( 1 << i ) ) ) a = Dp [a][i] ; } return ( a == b ) ; } int Query ( int a , int b ) { if ( w [a] < w [b] ) swap ( a , b ) ; int l = w [a] - w [b] ; int ans = Best [a] ; for ( int i = 0 ; i < 20 ; i ++ ) { if ( ( l & ( 1 << i ) ) ) { ans = min ( ans , Mn [a][i] ) ; a = Dp [a][i] ; } } return ans ; } int main () { scanf("%d%d%d%d",&n,&m,&q,&Root) ; Root -- ; for ( int i = 0 ; i < n - 1 ; i ++ ) { int a , b , c ; scanf("%d%d%d",&a,&b,&c) ; a -- , b -- ; v [a] .pb ( { b , c } ) ; v [b] .pb ( { a , c } ) ; E [i] = { a , b } ; } for ( int i = 0 ; i < m ; i ++ ) { int x ; scanf("%d",&x) , x -- ; Yes [x] = 1 ; } Fill ( Root , Root , 0 ) ; for ( int Node = 0 ; Node < n ; Node ++ ) { if ( Best [Node] != 1e9 ) { Best [Node] += -2 * Dis [Node] ; } } for ( int Node = 0 ; Node < n ; Node ++ ) { Mn [Node][0] = min ( Best [Node] , Best [ Dp [Node][0] ] ) ; } for ( int j = 1 ; j < 20 ; j ++ ) { for ( int i = 0 ; i < n ; i ++ ) { Dp [i][j] = Dp [ Dp [i][j-1] ][j-1] ; Mn [i][j] = min ( Mn [i][j-1] , Mn [ Dp [i][j-1] ][j-1] ) ; } } for ( int i = 0 ; i < n - 1 ; i ++ ) { if ( w [ E [i].fi ] > w [ E [i] .se ] ) swap ( E [i].fi , E [i] .se ) ; } while ( q -- ) { int e , b ; scanf("%d%d",&e,&b) ; e -- , b -- ; int a = E [e] .se ; if ( Check ( a , b ) && w [a] <= w [b] ) { int x = min ( Query ( a , b ) , Best [b] ) + Dis [b] ; if ( x >= 1e8 ) puts("oo"); else printf("%d\n",x) ; } else puts("escaped"); } }

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp: In function 'int main()':
valley.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d",&n,&m,&q,&Root) ;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:75:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d%d",&a,&b,&c) ;
                 ~~~~~^~~~~~~~~~~~~~~~~~~
valley.cpp:83:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d",&x) , x -- ;
                 ~~~~~~~~~~~~~~~^~~~~~
valley.cpp:106:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d",&e,&b) ;
                 ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...