제출 #686433

#제출 시각아이디문제언어결과실행 시간메모리
686433GudStonks관광지 (IZhO14_shymbulak)C++17
0 / 100
40 ms10928 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ft first #define sd second const ll MOD = 1e9+7; ll n, used[200005], ver[200005], z[1000010], ti = 1; vector<ll>g[200005], cic; pair<ll, ll>t[1000010], arr[200005]; void dfs(ll v = 1, ll p = -1){ used[v] = 1; for(auto to : g[v]){ if(used[to] == 1 && to != p){ used[to] = 3; used[v] = 2; } else if(used[to] == 0){ dfs(to, v); if(used[to] == 2 && used[v] != 3){ used[v] = 2; } } else if(used[v] != 3 && to != p){ cout<<v<<" "<<to<<" "<<used[to]<<endl; } } if(used[v] == 3 || used[v] == 2) cic.push_back(v), ver[v] = ti++; } pair<ll, ll> dfs1(ll v, ll p = -1){ ll mx = 0, c = 1; for(auto to : g[v]){ if(to != p && used[to] == 1){ auto xx = dfs1(to, v); if(xx.ft > mx) mx = xx.ft, c = xx.sd; else if(xx.ft == mx) c += xx.sd; } } return {mx + 1, c}; } pair<ll, ll> combine(pair<ll, ll>l, pair<ll, ll>r){ if(l.ft > r.ft) return l; else if(r.ft > l.ft) return r; else return {l.ft, l.sd + r.sd}; } void build(ll v = 1, ll tl = 1, ll tr = n){ if(tl == tr) t[v] = arr[tl]; else{ ll tm = (tl + tr) / 2; build(v + v, tl, tm); build(v + v + 1, tm + 1, tr); t[v] = combine(t[v + v], t[v + v + 1]); } } void prp(ll v){ t[v].ft += z[v]; if(v + v <= 8e5){ z[v + v] += z[v]; z[v + v + 1] += z[v]; } z[v] = 0; } pair<ll, ll> get(ll l, ll r, ll v = 1, ll tl = 1, ll tr = n){ prp(v); if(tl > r || tr < l) return {0, 0}; if(l <= tl && tr <= r) return t[v]; ll tm = (tl + tr) / 2; return combine(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr)); } void upd(ll l, ll r, ll val, ll v = 1, ll tl = 1, ll tr = n){ prp(v); if(tl > r || tr < l) return; if(l <= tl && tr <= r){ z[v] += val; prp(v); return; } ll tm = (tl + tr) / 2; upd(l, r, val, v + v, tl, tm); upd(l, r, val, v + v + 1, tm + 1, tr); } set<ll>s; void fun(){ cin>>n; for(ll i = 1, a, b; i <= n; i++){ cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } dfs(); for(auto it : cic) arr[ver[it]] = dfs1(it), arr[ver[it]].ft--; n = cic.size(); for(ll i = 2; i <= n; i++)arr[i].ft += min(i - 1, n - i + 1); build(); map<ll, ll>mp; for(ll i = 1; i <= n; i++){ if(i > 1){ if(i + (n / 2) - 1 > n) upd(i, n, -1), upd(1, i + (n / 2) - 1 - n, -1); else upd(i, i + (n / 2) - 1, -1); ll xx = (((i - n / 2) - 1 + n) % n) + 1; if(xx + (n / 2) - 1 > n) upd(xx, n, 1), upd(1, xx + (n / 2) - 1 - n, 1); else upd(xx, xx + (n / 2) - 1, 1); } pair<ll, ll> x; if(i == 1) x = get(2, n); else if(i < n) x = combine(get(1, i - 1), get(i + 1, n)); else x = get(1, n - 1); s.insert(x.ft); mp[x.ft] += x.sd; } auto it = s.end();it--; cout<<mp[*it]; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int ttt = 1; //cin>>ttt; while(ttt--)fun(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...