Submission #359275

#TimeUsernameProblemLanguageResultExecution timeMemory
359275nicolaalexandraShymbulak (IZhO14_shymbulak)C++14
70 / 100
139 ms20972 KiB
#include <bits/stdc++.h> #define DIM 200010 #define DIMBUFF 7000000 using namespace std; struct segment_tree{ int maxi,maxi2; long long cnt,cnt2; /// cate noduri din arborele initial int lazy; } aint[DIM*4]; vector <int> L[DIM],s; vector <pair<int,int> > w; int viz[DIM],fth[DIM],f[DIM],v[DIM],dist[DIM]; pair <int,int> dp[DIM]; char buff[DIMBUFF]; int n,i,x,y,k,sol,pos; long long sol_cnt; void dfs (int nod, int tata){ viz[nod] = 1; s.push_back (nod); for (auto vecin : L[nod]){ if (vecin == tata) continue; if (!viz[vecin]) dfs (vecin,nod); else { if (viz[vecin] == 1){ int poz = s.size()-1; while (poz >= 0 && s[poz] != vecin){ v[++k] = s[poz]; poz--; } v[++k] = vecin; }}} s.pop_back(); viz[nod] = 2; /// nu mai e in stiva } void dfs2 (int nod, int tata){ for (auto vecin : L[nod]){ if (vecin != tata && !f[vecin]) dfs2 (vecin,nod); } dp[nod].second = 1; for (auto vecin : L[nod]){ if (vecin == tata || f[vecin]) continue; if (dp[nod].first + dp[vecin].first + 1 > sol){ sol = dp[nod].first + dp[vecin].first + 1; sol_cnt = 1LL * dp[nod].second * dp[vecin].second * 2; } else { if (dp[nod].first + dp[vecin].first + 1 == sol) sol_cnt += 1LL * dp[nod].second * dp[vecin].second * 2; } if (dp[vecin].first + 1 > dp[nod].first){ dp[nod].first = dp[vecin].first + 1; dp[nod].second = dp[vecin].second; } else { if (dp[vecin].first + 1 == dp[nod].first) dp[nod].second += dp[vecin].second; }}} void update_nod (int nod){ int fiu_st = nod<<1, fiu_dr = (nod<<1)|1; aint[nod] = aint[fiu_st]; if (aint[fiu_dr].maxi > aint[nod].maxi){ aint[nod].maxi2 = aint[nod].maxi; aint[nod].cnt2 = aint[nod].cnt; aint[nod].maxi = aint[fiu_dr].maxi; aint[nod].cnt = aint[fiu_dr].cnt; } else { if (aint[fiu_dr].maxi == aint[nod].maxi) aint[nod].cnt += aint[fiu_dr].cnt; else { if (aint[fiu_dr].maxi > aint[nod].maxi2){ aint[nod].maxi2 = aint[fiu_dr].maxi; aint[nod].cnt2 = aint[fiu_dr].cnt; } else { if (aint[fiu_dr].maxi == aint[nod].maxi2) aint[nod].cnt2 += aint[fiu_dr].cnt; }}} if (aint[fiu_dr].maxi2 > aint[nod].maxi2){ aint[nod].maxi2 = aint[fiu_dr].maxi2; aint[nod].cnt2 = aint[fiu_dr].cnt2; } else { if (aint[fiu_dr].maxi2 == aint[nod].maxi2) aint[nod].cnt2 += aint[fiu_dr].cnt2; } } void update_lazy (int nod, int st, int dr){ if (!aint[nod].lazy) return; if (st != dr){ int fiu_st = nod<<1, fiu_dr = (nod<<1)|1; aint[fiu_st].maxi += aint[nod].lazy; aint[fiu_st].maxi2 += aint[nod].lazy; aint[fiu_st].lazy += aint[nod].lazy; aint[fiu_dr].maxi += aint[nod].lazy; aint[fiu_dr].maxi2 += aint[nod].lazy; aint[fiu_dr].lazy += aint[nod].lazy; } aint[nod].lazy = 0; } void build (int nod, int st, int dr){ if (st == dr){ aint[nod].maxi = dist[st]; aint[nod].cnt = dp[v[st]].second; return; } int mid = (st+dr)>>1; build (nod<<1,st,mid); build ((nod<<1)|1,mid+1,dr); update_nod (nod); } void update (int nod, int st, int dr, int x, int y, int val){ if (x > y) return; update_lazy (nod,st,dr); if (x <= st && dr <= y){ aint[nod].maxi += val; aint[nod].maxi2 += val; aint[nod].lazy += val; update_lazy (nod,st,dr); return; } int mid = (st+dr)>>1; if (x <= mid) update (nod<<1,st,mid,x,y,val); if (y > mid) update ((nod<<1)|1,mid+1,dr,x,y,val); update_lazy (nod<<1,st,mid); update_lazy ((nod<<1)|1,mid+1,dr); update_nod (nod); } int get_nr (){ while (!(buff[pos] >= '0' && buff[pos] <= '9')) pos++; int nr = 0; while (buff[pos] >= '0' && buff[pos] <= '9'){ nr = nr * 10 + buff[pos] - '0'; pos++; } return nr; } int main (){ //FILE *fin = fopen ("date.in","r"); //FILE *fout = fopen ("date.out","w"); FILE *fin = stdin; FILE *fout = stdout; fread (buff,1,DIMBUFF,fin); n = get_nr(); for (i=1;i<=n;i++){ x = get_nr(), y = get_nr(); L[x].push_back(y); L[y].push_back(x); } dfs (1,0); for (i=1;i<=k;i++) f[v[i]] = 1; sol = -1; for (i=1;i<=k;i++) dfs2 (v[i],0); /// distantele int st = 2, dr = k, nr = 1; while (st < dr){ dist[st] = dist[dr] = nr; nr++; st++, dr--; } if (k % 2 == 0) dist[st] = nr; for (i=1;i<=k;i++) dist[i] += dp[v[i]].first; /// trb sa retin doua maxime in aint?? build (1,1,k); /// lg ciclu impara => nu pot sa am mai mult de un drum minim intre doua noduri int poz = k / 2 + 1; for (i=1;i<=k;i++){ /// query if (aint[1].maxi != dp[v[i]].first){ if (aint[1].maxi + dp[v[i]].first > sol){ sol = aint[1].maxi + dp[v[i]].first; sol_cnt = 1LL * dp[v[i]].second * aint[1].cnt; } else { if (aint[1].maxi + dp[v[i]].first == sol) sol_cnt += 1LL * dp[v[i]].second * aint[1].cnt; } } else { if (aint[1].cnt - dp[v[i]].second){ if (aint[1].maxi * 2 > sol){ sol = aint[1].maxi * 2; sol_cnt = 1LL * dp[v[i]].second * (aint[1].cnt - dp[v[i]].second); } else { if (aint[1].maxi * 2 == sol) sol_cnt += 1LL * dp[v[i]].second * (aint[1].cnt - dp[v[i]].second); } } else { /// iau al doilea maxim if (dp[v[i]].first + aint[1].maxi2 > sol){ sol = dp[v[i]].first + aint[1].maxi2; sol_cnt = 1LL * dp[v[i]].second * aint[1].cnt2; } else { if (dp[v[i]].first + aint[1].maxi2 == sol) sol_cnt += 1LL * dp[v[i]].second * aint[1].cnt2; }}} /// update if (k % 2){ /// lg impara if (poz >= k/2 + 1){ update (1,1,k,i+1,poz,-1); update (1,1,k,poz+2,k,1); if (poz == k) update (1,1,k,2,i,1); else update (1,1,k,1,i,1); } else { update (1,1,k,i+1,k,-1); update (1,1,k,poz+2,i,1); update (1,1,k,1,poz,-1); } } else { if (poz >= k/2 + 1){ update (1,1,k,i+1,poz,-1); update (1,1,k,poz+1,n,1); update (1,1,k,1,i,1); } else { update (1,1,k,i+1,n,-1); update (1,1,k,poz+1,i,1); update (1,1,k,1,poz,-1); } } poz++; if (poz > k) poz = 1; } /// trebuie sa mai verific si perechile la care pot sa ajung in doua moduri if (k % 2 == 0){ for (i=1;i<=k;i++){ int poz = i + k/2; if (poz > k) poz -= k; if (dp[v[i]].first + dp[v[poz]].first + k/2 > sol){ sol = dp[v[i]].first + dp[v[poz]].first + k/2; sol_cnt = 1LL * dp[v[i]].second * dp[v[poz]].second; } else { if (dp[v[i]].first + dp[v[poz]].first + k/2 == sol) sol_cnt += 1LL * dp[v[i]].second * dp[v[poz]].second; } } } fprintf(fout,"%lld",sol_cnt/2); //cout<<sol_cnt / 2; return 0; }

Compilation message (stderr)

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:181:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  181 |     fread (buff,1,DIMBUFF,fin);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...