제출 #91190

#제출 시각아이디문제언어결과실행 시간메모리
91190daniel_02관광지 (IZhO14_shymbulak)C++14
100 / 100
1035 ms39568 KiB
#include <bits/stdc++.h> #define fr first #define pb push_back #define sc second #define ll long long using namespace std; const int N = 2e5 + 7; const int inf = 1e9 + 7; vector<int>g[N]; int c[N]; set<int, greater<int>>st1; set<int, greater<int>>st2; int mp1[N]; int mp2[N]; ll cnt[N]; int qt[N], tin[N], cn, fup[N]; ll mx = -1; map<pair<int, int>, bool>is_b; bool us[N]; int ver; int cycn; void dfs(int v, int p) { tin[v] = fup[v] = ++cn; us[v] = 1; for (int i = 0; i < g[v].size(); i++) { int to = g[v][i]; if (to == p)continue; if (us[to]) { fup[v] = min(fup[v], tin[to]); } else { dfs(to, v); fup[v] = min(fup[v], fup[to]); if (fup[to] > tin[v]) is_b[{v, to}] = 1, is_b[{to, v}] = 1; else ver = to; } } } pair<int, int> deep(int v, int p) { ll mxx = -1, mx1 = -1; ll eq = 1, eq1 = 1; ll col = 0, sm = 0; for (int i = 0; i < g[v].size(); i++) { int to = g[v][i]; if (to == p || !is_b[{v, to}])continue; pair<ll, ll> q = deep(to, v); if (mxx < q.fr) { eq1 = eq; mx1 = mxx; mxx = q.fr; eq = q.sc; sm = q.sc; } else { if (q.fr == mxx){ eq += q.sc; col += (q.sc * sm); sm += q.sc; } if (q.fr == mx1) eq1 += q.sc; if (q.fr > mx1) eq1 = q.sc; mx1 = max(mx1, q.fr * 1LL); } } mxx++; mx1++; if (mxx != mx1) { col = eq * eq1; } mx = max(mxx + mx1, mx); cnt[mxx + mx1] += col; return {mxx, eq}; } void dfs1(int v, int p, int id) { us[v] = 1; cycn++; us[v] = 1; int mx = 0; int cnt = 0; pair<int, int>q = deep(v, p); mx = q.fr, cnt = q.sc; c[id] = mx; qt[id] = cnt; for (int i = 0; i < g[v].size(); i++) { int to = g[v][i]; if (us[to] || is_b[{v, to}])continue; dfs1(to, v, id + 1); } } void dfs2(int v, int p, int id) { us[v] = 1; if (id != 0) { ll len = (*st1.begin()) + id + c[id]; mx = max(mx, len); cnt[len] += (mp1[len - id - c[id]] * 1LL * qt[id]); if (st2.size()) { len = (*st2.begin()) - id + c[id]; mx = max(mx, len); cnt[len] += (mp2[len + id - c[id]] * 1LL * qt[id]); } } st1.insert(c[id] - id); mp1[c[id] - id] += qt[id]; int prev = cycn / 2; if (id >= prev) { mp1[c[id - prev] - id + prev] -= qt[id - prev]; if (mp1[c[id - prev] - id + prev] == 0) st1.erase(c[id - prev] - id + prev); if (cycn % 2){ st2.insert(c[id - prev] + cycn + id - prev); mp2[c[id - prev] + cycn + id - prev] += qt[id - prev]; } } if (cycn % 2 == 0 && id >= prev - 1) { st2.insert(cycn + (id - prev + 1) + c[id - prev + 1]); mp2[cycn + (id - prev + 1) + c[id - prev + 1]] += qt[id - prev + 1]; } for (int i = 0; i < g[v].size(); i++) { int to = g[v][i]; if (is_b[{v, to}] || us[to])continue; dfs2(to, v, id + 1); } } main() { int n; cin >> n; for (int i = 1; i <= n; i++) { int a, b; scanf("%d%d", &a, &b); g[a].pb(b); g[b].pb(a); } dfs(1, 0); memset(us, 0, sizeof(us)); dfs1(ver, 0, 0); memset(us, 0, sizeof(us)); dfs2(ver, 0, 0); cout << cnt[mx] << endl; } /* * Find Bridges * Assign c[i]s (length of subtree) and q[i] number of them and cyc -> length of cycle * Dance */

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

shymbulak.cpp: In function 'void dfs(int, int)':
shymbulak.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'std::pair<int, int> deep(int, int)':
shymbulak.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs1(int, int, int)':
shymbulak.cpp:102:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs2(int, int, int)':
shymbulak.cpp:142:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
shymbulak.cpp: At global scope:
shymbulak.cpp:149:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:158:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...