제출 #319388

#제출 시각아이디문제언어결과실행 시간메모리
319388Trickster관광지 (IZhO14_shymbulak)C++14
0 / 100
228 ms35064 KiB
//Suleyman Atayew #include <algorithm> #include <iostream> #include <string.h> #include <stdio.h> #include <vector> #include <queue> #include <cmath> #include <map> #include <set> #define N 200010 #define ff first #define ss second #define pb push_back #define ll long long #define mod 1000000007 #define pii pair <ll, ll> #define sz(a) (ll)(a.size()) ll bigmod(ll a, ll b) { if(b==0)return 1; ll ret = bigmod(a, b/2); return ret * ret % mod * (b%2 ? a : 1) % mod; } using namespace std; ll n, a, b, sz; map <pii, ll> M; ll vis[N], L[N*4]; pii p[N], H[N][5], S[N*4]; vector <ll> E[N], arr, v, T[N]; void dfs(ll nd, ll pr) { arr.pb(nd); vis[nd] = vis[pr]+1; for(auto i: E[nd]) { if(i == pr) continue; if(vis[i]) { for(ll h = vis[i]-1; h < vis[nd]; h++) v.pb(arr[h]); return; } dfs(i, nd); if(!v.empty()) return; } arr.pop_back(); vis[nd] = 0; } void dfs2(ll nd) { vis[nd] = 1; for(auto i: T[nd]) { if(vis[i]) continue; dfs2(i); if(H[nd][0].ff < H[i][0].ff) H[nd][1] = H[nd][0], H[nd][0] = {H[i][0].ff, 0}; if(H[nd][0].ff == H[i][0].ff) H[nd][0].ss += H[i][0].ss; else { if(H[nd][1].ff < H[i][0].ff) H[nd][1] = {H[i][0].ff, 0}; if(H[nd][1].ff == H[i][0].ff) H[nd][1].ss += H[i][0].ss; } } H[nd][0] = {H[nd][0].ff+1, max(1LL, H[nd][0].ss)}; H[nd][1] = {H[nd][1].ff+1, max(1LL, H[nd][1].ss)}; } void com(ll node) { if(S[node*2].ff < S[node*2+1].ff) S[node] = S[node*2+1]; if(S[node*2].ff > S[node*2+1].ff) S[node] = S[node*2]; if(S[node*2].ff == S[node*2+1].ff) S[node] = {S[node*2].ff, S[node*2].ss + S[node*2+1].ss}; } void build(ll l, ll r, ll node) { if(l == r) { S[node] = p[l]; return; } build(l, (l+r)/2, node*2); build((l+r)/2+1, r, node*2+1); com(node); } void shift(ll node, ll to) { L[to] += L[node]; S[to].ff += L[node]; } void upd(ll a, ll b, ll x, ll l, ll r, ll node) { if(l > b || r < a) return; if(l >= a && r <= b) { S[node].ff += x; L[node] += x; return; } shift(node, node*2); shift(node, node*2+1); L[node] = 0; upd(a, b, x, l, (l+r)/2, node*2); upd(a, b, x, (l+r)/2+1, r, node*2+1); com(node); } void upd2(ll pos, double x, ll l, ll r, ll node) { if(l == r) { S[node].ss *= x; return; } shift(node, node*2); shift(node, node*2+1); L[node] = 0; if(pos <= (l+r)/2) upd2(pos, x, l, (l+r)/2, node*2); else upd2(pos, x, (l+r)/2+1, r, node*2+1); com(node); } pii upd3(ll pos, pii x, ll l, ll r, ll node) { if(l == r) { pii a = S[node]; S[node] = x; return a; } shift(node, node*2); shift(node, node*2+1); L[node] = 0; pii ret; if(pos <= (l+r)/2) ret = upd3(pos, x, l, (l+r)/2, node*2); else ret = upd3(pos, x, (l+r)/2+1, r, node*2+1); com(node); return ret; } void job(ll l, ll r, ll x) { if(r > sz) r -= sz; if(l > sz) l -= sz; if(r >= l) upd(l, r, x, 1, sz, 1); else { upd(l, sz, x, 1, sz, 1); upd(1, r, x, 1, sz, 1); } } int main() { cin >> n; for(ll i = 1; i <= n; i++) { cin >> a >> b; E[a].pb(b); E[b].pb(a); p[i] = {a, b}; } dfs(1, 0); sz = v.size(); M[{v[0], v.back()}] = M[{v.back(), v[0]}] = 1; for(ll i = 1; i < v.size(); i++) M[{v[i], v[i-1]}] = M[{v[i-1], v[i]}] = 1; for(ll i = 1; i <= n; i++) { if(M[p[i]]) continue; T[p[i].ff].pb(p[i].ss); T[p[i].ss].pb(p[i].ff); } memset(vis, 0, sizeof(vis)); for(auto i: v) dfs2(i); for(ll i = 1; i <= sz; i++) p[i] = H[v[i-1]][0]; for(ll i = 2, h = sz; i < h; i++, h--) p[i].ff += i-1, p[h].ff += i-1; if(sz%2 == 0) p[sz/2+1].ff += sz/2; build(1, sz, 1); ll l = 2, lm = (sz-1)/2, pos = -1, last = -1, mx = 0, ans = 0; if(sz%2 == 0) pos = sz/2+1; for(ll i = 1; i <= sz; i++) { pii cur = upd3(i, {0, 0}, 1, sz, 1); if(last != -1) upd2(last, 0.5, 1, sz, 1); if(pos != -1) upd2(pos, 2, 1, sz, 1); ll now = S[1].ff + H[v[i-1]][0].ff - 1; ll cnt = S[1].ss * H[v[i-1]][0].ss; if(mx < now) { mx = now; ans = 0; } if(mx == now) ans += cnt; upd3(i, cur, 1, sz, 1); job(l, l+lm, -1); job(sz-lm+i, i, 1); l++; if(pos == -1) continue; last = pos, pos++; if(pos > sz) pos -= sz; } for(auto i: v) { ll now = 0, cnt = 2, ok = 0; for(auto h: T[i]) if(H[h][0].ff == H[i][0].ff - 1) { ok ++; cnt *= H[h][0].ss; } if(ok <= 1) { now = H[i][1].ff + H[i][0].ff - 1; cnt = H[i][1].ss * H[i][0].ss * 2; } else { now = H[i][0].ff * 2 - 1; } if(mx < now) { mx = now; ans = 0; } if(mx == now) ans += cnt; } cout << ans/2; } /* 6 1 2 1 3 2 4 4 3 4 5 4 6 ------------------------- 4 4 1 2 1 3 1 4 4 3 ------------------------- 2 9 1 2 1 3 2 3 3 4 4 5 5 6 3 7 7 8 8 9 ------------------------ 1 8 1 2 3 4 5 6 7 8 2 4 4 7 7 5 5 2 ----------------------- 4 7 1 2 2 3 3 4 4 5 5 6 6 7 7 1 ---------------------- 7 12 1 3 2 3 7 4 8 4 9 5 10 5 12 6 11 6 3 4 4 5 5 6 6 3 --------------------- 16 */

컴파일 시 표준 에러 (stderr) 메시지

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:186:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for(ll i = 1; i < v.size(); i++) M[{v[i], v[i-1]}] = M[{v[i-1], v[i]}] = 1;
      |                   ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...