Submission #315474

#TimeUsernameProblemLanguageResultExecution timeMemory
315474DymoUntitled (POI11_dyn)C++14
70 / 100
2289 ms44180 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define ll int #define pll pair<ll,ll> #define ff first #define ss second #define endl "\n" const ll maxn=3e5+100; const ll mod =1e9 + 7 ; const ll base=3e9; ll nw[maxn]; ll a[maxn]; ll cnt[maxn]; ll par[maxn]; ll n, m; ll cocan[maxn]; ll colua[maxn]; bool chk1[maxn]; bool chk2[maxn]; vector<ll> adj[maxn]; vector<ll> adj1[maxn]; void dfs(ll u,ll par1) { par[u]=par1; for (auto to:adj[u]) { if (to==par1) continue; cnt[u]++; dfs(to,u); } } bool chk(ll mid) { queue<ll> q; for (int i=1; i<=n; i++) { cnt[i]=0; chk1[i]=0; chk2[i]=0; cocan[i]=0; colua[i]=0; adj1[i].clear(); } dfs(1,0); for (int i=1; i<=n; i++) { if (cnt[i]==0) { q.push(i); } } ll ans=0; while (!q.empty()) { auto p=q.front(); q.pop(); bool chklua=false; bool chkcan=false; ll solua=0; ll socan=0; while (1) { if (chkcan==true) { socan++; } if (chklua==true) { solua--; } if (solua<0) { solua=0; chklua=0; } if (chk1[p]==true) { chklua=true; solua=max(solua,colua[p]); } if (chk2[p]==true) { chkcan=true; socan=max(socan,cocan[p]); } if (a[p]) { chkcan=true; socan=max(socan,0); } if (chkcan&&chklua) { if (solua>=socan) { chkcan=false; socan=0; } } if (chkcan&&socan==mid) { chklua=true; solua=mid; ans++; socan=0; chkcan=0; } chk1[p]=chklua; chk2[p]=chkcan; colua[p]=solua; cocan[p]=socan; for (auto to:adj1[p]) { chkcan=chk2[to]; chklua=chk1[to]; solua=colua[to]; socan=cocan[to]; if (chkcan==true) { socan++; } if (chklua==true) { solua--; } if (solua<0) { solua=0; chklua=0; } if (chk1[p]==true) { chklua=true; solua=max(solua,colua[p]); } if (chk2[p]==true) { chkcan=true; socan=max(socan,cocan[p]); } if (a[p]) { chkcan=true; socan=max(socan,0); } if (chkcan&&chklua) { if (solua>=socan) { chkcan=false; socan=0; } } if (chkcan&&socan==mid) { chklua=true; solua=mid; ans++; socan=false; chkcan=false; } chk1[p]=chklua; chk2[p]=chkcan; colua[p]=solua; } if (par[p]==-1) break; cnt[par[p]]--; if (cnt[par[p]]) { adj1[par[p]].pb(p); break; } p=par[p]; } } ans=ans+chk2[1]; if (ans<=m) return true; return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen("girth.t", "r")) { freopen("girth.inp", "r", stdin); freopen("girth.ans", "w", stdout) ; } cin>>n>>m ; for (int i=1; i<=n; i++) { cin>>a[i]; } for (int i=1; i<=n-1; i++) { ll x, y; cin>>x>> y; adj[x].pb(y); adj[y].pb(x); } ll l=0, h= n; while (l<=h) { ll mid=(l+h)/2; if (chk(mid)) { h=mid-1; } else { l=mid+1; } } cout <<l; }

Compilation message (stderr)

dyn.cpp:13:15: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+9' to '2147483647' [-Woverflow]
   13 | const ll base=3e9;
      |               ^~~
dyn.cpp: In function 'int main()':
dyn.cpp:198:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  198 |         freopen("girth.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dyn.cpp:199:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  199 |         freopen("girth.ans", "w", stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#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...