제출 #91181

#제출 시각아이디문제언어결과실행 시간메모리
91181daniel_02관광지 (IZhO14_shymbulak)C++17
100 / 100
1143 ms41300 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; map<int, ll>mp1; map<int, ll>mp2; map<ll, ll>cnt; 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); } //cout << v << " " << mx1 << " <-> " << mxx << " " << eq << " " << eq1 << " " << col << endl; } mxx++; mx1++; if (mxx != mx1) { col = eq * eq1; } //cout << v << " " << mxx << " " << mx1 << " " << eq << " " << eq1 << " " << col << endl; mx = max(mxx + mx1, mx); cnt[mxx + mx1] += col; //cout << v << " " << mxx + mx1 << " " << cnt[mxx + mx1] << " " << mx << endl; 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]); //cout << v << " " << id << " " << len << " " << mp1[len - id - c[id]] * 1LL * qt[id] << endl; if (st2.size()) { len = (*st2.begin()) - id + c[id]; mx = max(mx, len); cnt[len] += (mp2[len + id - c[id]] * 1LL * qt[id]); //cout << v << " " << id << " " << len << " " << mp2[len + id - c[id]] * 1LL * qt[id] << endl; } //cout << endl; } 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); //cout << " <<<- " << c[id - prev] + cycn + id - prev << " " << qt[id - prev] << endl; 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]); //cout << " ->>> " << cycn + (id - prev + 1) + c[id - prev + 1] << " " << qt[id - prev + 1] << endl; 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 << mx << endl; 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 */ /* 12 5 11 5 4 4 3 3 6 11 7 11 10 4 9 11 12 4 1 5 8 11 2 6 2 */

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

shymbulak.cpp: In function 'void dfs(int, int)':
shymbulak.cpp:30: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:54: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:104: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:149: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:156:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:165: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...