| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 876578 | imarn | Valley (BOI19_valley) | C++14 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define l long long
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define f first
#define s second
#define vi vector<int>
#define vll vector<long long>
#define vpii vector<pii>
using namespace std;
const int N=1e5+5;
vector<pii>g[N];
ll d[N]{0},pr[N][18],dp[N][19],dep[N]{0},node[N]{0};
pii ro[N];
int tin[N]{0},tout[N]{0};
int t=0;
ll dfs(int u,int p,int l){
pr[u][0]=p;dep[u]=l;ll mn=1e17;
for(int i=1;i<=17;i++)pr[u][i]=pr[pr[u][i-1]][i-1];
if(node[u])mn=d[u];
tin[u]=++t;
for(auto v:g[u]){
if(v.f==p)continue;
d[v.f]=d[u]+v.s;
mn=min(mn,dfs(v.f,u,l+1));
}dp[u][0] = mn-2*d[u];tout[u]=t;
return mn;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,s,q,e;cin>>n>>s>>q>>e;
for(int i=1,u,v,w;i<=n-1;i++)cin>>u>>v>>w,g[u].pb({v,w}),g[v].pb({u,w}),ro[i]={u,v};
for(int i=1,u;i<=s;i++)cin>>u,node[u]=1;
dfs(e,e,0);
for(int j=1;j<=18;j++)for(int i=1;i<=n;i++)dp[i][j]=min(dp[i][j-1],dp[pr[i][j-1]][j-1]);
while(q--){
int i,r,x,y;cin>>i>>r;tie(x,y)=ro[i];if(dep[x]<dep[y])swap(x,y);ll ans=1e17;int cur=r;
if(!(tin[x]<=tin[r]&&tin[r]<=tout[x])){cout<<"escaped\n";continue;}
for(int i=17;i>=0;i--)if(dep[x]<=dep[pr[cur][i]])ans=min(ans,dp[cur][i+1]+d[r]),cur=pr[cur][i];
ans=min(ans,d[r]+dp[cur][0]);
if(ans>=1e15)cout<<"oo\n";
else cout<<ans<<"\n";
}
}
Compilation message (stderr)
valley.cpp:3:18: error: 'll' was not declared in this scope; did you mean 'vll'?
3 | #define pii pair<ll,ll>
| ^~
valley.cpp:15:8: note: in expansion of macro 'pii'
15 | vector<pii>g[N];
| ^~~
valley.cpp:3:21: error: 'll' was not declared in this scope; did you mean 'vll'?
3 | #define pii pair<ll,ll>
| ^~
valley.cpp:15:8: note: in expansion of macro 'pii'
15 | vector<pii>g[N];
| ^~~
valley.cpp:3:23: error: template argument 1 is invalid
3 | #define pii pair<ll,ll>
| ^
valley.cpp:15:8: note: in expansion of macro 'pii'
15 | vector<pii>g[N];
| ^~~
valley.cpp:3:23: error: template argument 2 is invalid
3 | #define pii pair<ll,ll>
| ^
valley.cpp:15:8: note: in expansion of macro 'pii'
15 | vector<pii>g[N];
| ^~~
valley.cpp:15:11: error: template argument 1 is invalid
15 | vector<pii>g[N];
| ^
valley.cpp:15:11: error: template argument 2 is invalid
valley.cpp:16:1: error: 'll' does not name a type; did you mean 'vll'?
16 | ll d[N]{0},pr[N][18],dp[N][19],dep[N]{0},node[N]{0};
| ^~
| vll
valley.cpp:16:11: error: expected unqualified-id before ',' token
16 | ll d[N]{0},pr[N][18],dp[N][19],dep[N]{0},node[N]{0};
| ^
valley.cpp:16:21: error: expected constructor, destructor, or type conversion before ',' token
16 | ll d[N]{0},pr[N][18],dp[N][19],dep[N]{0},node[N]{0};
| ^
valley.cpp:16:31: error: expected constructor, destructor, or type conversion before ',' token
16 | ll d[N]{0},pr[N][18],dp[N][19],dep[N]{0},node[N]{0};
| ^
valley.cpp:16:38: error: expected constructor, destructor, or type conversion before '{' token
16 | ll d[N]{0},pr[N][18],dp[N][19],dep[N]{0},node[N]{0};
| ^
valley.cpp:16:41: error: expected unqualified-id before ',' token
16 | ll d[N]{0},pr[N][18],dp[N][19],dep[N]{0},node[N]{0};
| ^
valley.cpp:16:49: error: expected constructor, destructor, or type conversion before '{' token
16 | ll d[N]{0},pr[N][18],dp[N][19],dep[N]{0},node[N]{0};
| ^
valley.cpp:3:18: error: 'll' was not declared in this scope; did you mean 'vll'?
3 | #define pii pair<ll,ll>
| ^~
valley.cpp:17:1: note: in expansion of macro 'pii'
17 | pii ro[N];
| ^~~
valley.cpp:3:21: error: 'll' was not declared in this scope; did you mean 'vll'?
3 | #define pii pair<ll,ll>
| ^~
valley.cpp:17:1: note: in expansion of macro 'pii'
17 | pii ro[N];
| ^~~
valley.cpp:3:23: error: template argument 1 is invalid
3 | #define pii pair<ll,ll>
| ^
valley.cpp:17:1: note: in expansion of macro 'pii'
17 | pii ro[N];
| ^~~
valley.cpp:3:23: error: template argument 2 is invalid
3 | #define pii pair<ll,ll>
| ^
valley.cpp:17:1: note: in expansion of macro 'pii'
17 | pii ro[N];
| ^~~
valley.cpp:20:1: error: 'll' does not name a type; did you mean 'vll'?
20 | ll dfs(int u,int p,int l){
| ^~
| vll
valley.cpp: In function 'int main()':
valley.cpp:6:12: error: request for member 'push_back' in 'g[u]', which is of non-class type 'int'
6 | #define pb push_back
| ^~~~~~~~~
valley.cpp:35:52: note: in expansion of macro 'pb'
35 | for(int i=1,u,v,w;i<=n-1;i++)cin>>u>>v>>w,g[u].pb({v,w}),g[v].pb({u,w}),ro[i]={u,v};
| ^~
valley.cpp:6:12: error: request for member 'push_back' in 'g[v]', which is of non-class type 'int'
6 | #define pb push_back
| ^~~~~~~~~
valley.cpp:35:67: note: in expansion of macro 'pb'
35 | for(int i=1,u,v,w;i<=n-1;i++)cin>>u>>v>>w,g[u].pb({v,w}),g[v].pb({u,w}),ro[i]={u,v};
| ^~
valley.cpp:35:87: error: cannot convert '<brace-enclosed initializer list>' to 'int' in assignment
35 | for(int i=1,u,v,w;i<=n-1;i++)cin>>u>>v>>w,g[u].pb({v,w}),g[v].pb({u,w}),ro[i]={u,v};
| ^
valley.cpp:36:35: error: 'node' was not declared in this scope
36 | for(int i=1,u;i<=s;i++)cin>>u,node[u]=1;
| ^~~~
valley.cpp:37:5: error: 'dfs' was not declared in this scope; did you mean 'ffs'?
37 | dfs(e,e,0);
| ^~~
| ffs
valley.cpp:38:48: error: 'dp' was not declared in this scope
38 | for(int j=1;j<=18;j++)for(int i=1;i<=n;i++)dp[i][j]=min(dp[i][j-1],dp[pr[i][j-1]][j-1]);
| ^~
valley.cpp:38:75: error: 'pr' was not declared in this scope; did you mean 'pb'?
38 | for(int j=1;j<=18;j++)for(int i=1;i<=n;i++)dp[i][j]=min(dp[i][j-1],dp[pr[i][j-1]][j-1]);
| ^~
| pb
valley.cpp:40:44: error: no match for 'operator=' (operand types are 'std::tuple<int&, int&>' and 'int')
40 | int i,r,x,y;cin>>i>>r;tie(x,y)=ro[i];if(dep[x]<dep[y])swap(x,y);ll ans=1e17;int cur=r;
| ^
In file included from /usr/include/c++/10/functional:54,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:71,
from valley.cpp:1:
/usr/include/c++/10/tuple:1173:7: note: candidate: 'std::tuple<_T1, _T2>& std::tuple<_T1, _T2>::operator=(typename std::conditional<__assignable<const _T1&, const _T2&>(), const std::tuple<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = int&; _T2 = int&; typename std::conditional<__assignable<const _T1&, const _T2&>(), const std::tuple<_T1, _T2>&, const std::__nonesuch&>::type = const std::tuple<int&, int&>&]'
1173 | operator=(typename conditional<__assignable<const _T1&, const _T2&>(),
| ^~~~~~~~
/usr/include/c++/10/tuple:1175:35: note: no known conversion for argument 1 from 'int' to 'std::conditional<true, const std::tuple<int&, int&>&, const std::__nonesuch&>::type' {aka 'const std::tuple<int&, int&>&'}
1173 | operator=(typename conditional<__assignable<const _T1&, const _T2&>(),
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1174 | const tuple&,
| ~~~~~~~~~~~~~
1175 | const __nonesuch&>::type __in)
| ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
/usr/include/c++/10/tuple:1184:7: note: candidate: 'std::tuple<_T1, _T2>& std::tuple<_T1, _T2>::operator=(typename std::conditional<__assignable<_T1, _T2>(), std::tuple<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = int&; _T2 = int&; typename std::conditional<__assignable<_T1, _T2>(), std::tuple<_T1, _T2>&&, std::__nonesuch&&>::type = std::tuple<int&, int&>&&]'
1184 | operator=(typename conditional<__assignable<_T1, _T2>(),
| ^~~~~~~~
/usr/include/c++/10/tuple:1186:30: note: no known conversion for argument 1 from 'int' to 'std::conditional<true, std::tuple<int&, int&>&&, std::__nonesuch&&>::type' {aka 'std::tuple<int&, int&>&&'}
1184 | operator=(typename conditional<__assignable<_T1, _T2>(),
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1185 | tuple&&,
| ~~~~~~~~
1186 | __nonesuch&&>::type __in)
| ~~~~~~~~~~~~~~~~~~~~^~~~
/usr/include/c++/10/tuple:1196:2: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<__assignable<const _U1&, const _U2&>(), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(const std::tuple<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = int&; _T2 = int&]'
1196 | operator=(const tuple<_U1, _U2>& __in)
| ^~~~~~~~
/usr/include/c++/10/tuple:1196:2: note: template argument deduction/substitution failed:
valley.cpp:40:44: note: mismatched types 'const std::tuple<_T1, _T2>' and 'int'
40 | int i,r,x,y;cin>>i>>r;tie(x,y)=ro[i];if(dep[x]<dep[y])swap(x,y);ll ans=1e17;int cur=r;
| ^
In file included from /usr/include/c++/10/functional:54,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:71,
from valley.cpp:1:
/usr/include/c++/10/tuple:1206:2: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<__assignable<_U1, _U2>(), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(std::tuple<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = int&; _T2 = int&]'
1206 | operator=(tuple<_U1, _U2>&& __in)
| ^~~~~~~~
/usr/include/c++/10/tuple:1206:2: note: template argument deduction/substitution failed:
valley.cpp:40:44: note: mismatched types 'std::tuple<_T1, _T2>' and 'int'
40 | int i,r,x,y;cin>>i>>r;tie(x,y)=ro[i];if(dep[x]<dep[y])swap(x,y);ll ans=1e17;int cur=r;
| ^
In file included from /usr/include/c++/10/functional:54,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:71,
from valley.cpp:1:
/usr/include/c++/10/tuple:1216:2: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<__assignable<const _U1&, const _U2&>(), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = int&; _T2 = int&]'
1216 | operator=(const pair<_U1, _U2>& __in)
| ^~~~~~~~
/usr/include/c++/10/tuple:1216:2: note: template argument deduction/substitution failed:
valley.cpp:40:44: note: mismatched types 'const std::pair<_T1, _T2>' and 'int'
40 | int i,r,x,y;cin>>i>>r;tie(x,y)=ro[i];if(dep[x]<dep[y])swap(x,y);ll ans=1e17;int cur=r;
| ^
In file included from /usr/include/c++/10/functional:54,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:71,
from valley.cpp:1:
/usr/include/c++/10/tuple:1227:2: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<__assignable<_U1, _U2>(), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = int&; _T2 = int&]'
1227 | operator=(pair<_U1, _U2>&& __in)
| ^~~~~~~~
/usr/include/c++/10/tuple:1227:2: note: template argument deduction/substitution failed:
valley.cpp:40:44: note: mismatched types 'std::pair<_T1, _T2>' and 'int'
40 | int i,r,x,y;cin>>i>>r;tie(x,y)=ro[i];if(dep[x]<dep[y])swap(x,y);ll ans=1e17;int cur=r;
| ^
valley.cpp:40:49: error: 'dep' was not declared in this scope
40 | int i,r,x,y;cin>>i>>r;tie(x,y)=ro[i];if(dep[x]<dep[y])swap(x,y);ll ans=1e17;int cur=r;
| ^~~
valley.cpp:40:73: error: 'll' was not declared in this scope; did you mean 'vll'?
40 | int i,r,x,y;cin>>i>>r;tie(x,y)=ro[i];if(dep[x]<dep[y])swap(x,y);ll ans=1e17;int cur=r;
| ^~
| vll
valley.cpp:42:34: error: 'dep' was not declared in this scope
42 | for(int i=17;i>=0;i--)if(dep[x]<=dep[pr[cur][i]])ans=min(ans,dp[cur][i+1]+d[r]),cur=pr[cur][i];
| ^~~
valley.cpp:42:46: error: 'pr' was not declared in this scope; did you mean 'r'?
42 | for(int i=17;i>=0;i--)if(dep[x]<=dep[pr[cur][i]])ans=min(ans,dp[cur][i+1]+d[r]),cur=pr[cur][i];
| ^~
| r
valley.cpp:42:58: error: 'ans' was not declared in this scope; did you mean 'abs'?
42 | for(int i=17;i>=0;i--)if(dep[x]<=dep[pr[cur][i]])ans=min(ans,dp[cur][i+1]+d[r]),cur=pr[cur][i];
| ^~~
| abs
valley.cpp:42:70: error: 'dp' was not declared in this scope
42 | for(int i=17;i>=0;i--)if(dep[x]<=dep[pr[cur][i]])ans=min(ans,dp[cur][i+1]+d[r]),cur=pr[cur][i];
| ^~
valley.cpp:42:83: error: 'd' was not declared in this scope
42 | for(int i=17;i>=0;i--)if(dep[x]<=dep[pr[cur][i]])ans=min(ans,dp[cur][i+1]+d[r]),cur=pr[cur][i];
| ^
valley.cpp:43:9: error: 'ans' was not declared in this scope; did you mean 'abs'?
43 | ans=min(ans,d[r]+dp[cur][0]);
| ^~~
| abs
valley.cpp:43:21: error: 'd' was not declared in this scope
43 | ans=min(ans,d[r]+dp[cur][0]);
| ^
valley.cpp:43:26: error: 'dp' was not declared in this scope
43 | ans=min(ans,d[r]+dp[cur][0]);
| ^~