Submission #1012356

#TimeUsernameProblemLanguageResultExecution timeMemory
1012356DucNguyen2007Mag (COCI16_mag)C++14
48 / 120
429 ms262144 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pll pair<ll,ll> #define fi first #define se second const int maxN=1e6+5; const ll inf=2e18; ll n,a[maxN+1],dp[maxN+1][2],g[maxN+1],mxn=0,g1[maxN+1]; vector<ll> adj[maxN+1],vec[maxN+1]; void dfs(ll u,ll p) { for(auto v:adj[u]) { if(v!=p) { vec[u].push_back(v); } } vector<vector<ll>> f(vec[u].size()+1,vector<ll>(2)); vector<ll> vt; for(int i=0;i<=vec[u].size();i++) { f[i][0]=f[i][1]=-inf; } f[0][0]=f[0][1]=(a[u]==1); ll mx=0; g1[u]=0; for(int i=0;i<vec[u].size();i++) { ll v=vec[u][i]; dfs(v,u); if(a[u]!=1) { f[i+1][0]=f[i+1][1]=0; } else { f[i+1][0]=max(f[i][0],dp[v][0]+1); f[i+1][1]=max(f[i][1],dp[v][0]+mx); } vt.push_back(dp[v][0]); mx=max(mx,f[i+1][0]); g1[u]=max(g1[u],dp[v][0]); } sort(vt.begin(),vt.end()); if(vt.size()>1) { g[u]=min(vt.back(),vt[vt.size()-2]); } else g[u]=0; dp[u][0]=f[vec[u].size()][0]; dp[u][1]=f[vec[u].size()][1]; } void Dfs(ll u,ll p,ll res) { if(a[u]==2) { mxn=max(mxn,min(res,g1[u])); res=0; } for(auto v:adj[u]) { if(v!=p) { Dfs(v,u,res+(a[v]==1)); } } } int main() { //freopen("","r",stdin); //freopen("","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ld mn=(ld)inf; ll sl,val; cin>>n; for(int i=1;i<n;i++) { ll u,v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } for(int i=1;i<=n;i++) { cin>>a[i]; if(mn>a[i]) { mn=a[i]; val=a[i]; sl=1; } } dfs(1,0); for(int i=1;i<=n;i++) { ld cur=(ld)1.0*max(dp[i][0],dp[i][1]); if(cur==0) { continue; } ld tmp=(ld)1.0*1/cur; //cout<<i<<" "<<cur<<'\n'; if(mn>tmp) { mn=tmp; val=1; sl=max(dp[i][0],dp[i][1]); } } for(int i=1;i<=n;i++) { if(a[i]==2) { ld cur=(ld)1.0*2*g[i]+1.0; ld tmp=(ld)1.0*2/cur; if(mn>tmp) { mn=tmp; val=2; sl=2*g[i]+1; } } } Dfs(1,0,(a[1]==1)); ld cur=(ld)1.0*2*mxn+1.0; ld tmp=(ld)1.0*2/cur; if(mn>tmp) { mn=tmp; val=2; sl=2*mxn+1; } cout<<val<<"/"<<sl; } /*3 1 2 2 3 1 2 1*/ /*5 1 2 1 3 2 4 3 5 2 1 1 1 1*/

Compilation message (stderr)

mag.cpp: In function 'void dfs(long long int, long long int)':
mag.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0;i<=vec[u].size();i++)
      |                 ~^~~~~~~~~~~~~~~
mag.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=0;i<vec[u].size();i++)
      |                 ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...