제출 #68592

#제출 시각아이디문제언어결과실행 시간메모리
68592ekrem관광지 (IZhO14_shymbulak)C++98
50 / 100
1574 ms34172 KiB
#include <bits/stdc++.h> #define st first #define nd second #define mp make_pair #define pb push_back #define N 1000005 using namespace std; typedef pair < int , int > ii; typedef pair < int , ii > iii; int n, m, cvp, kac = 1, u[N]; vector < int > g[N], b; ii c[N]; ii uz(int i, int j){ int uz1 = j - i; int uz2 = m - uz1; if(uz1 != uz2) return mp( min(uz1, uz2) , 1); return mp(uz1, 2); } void yap(int sonmx, int xx){ if(sonmx == cvp) kac += xx; if(sonmx > cvp){ cvp = sonmx; kac = xx; } } int dfs(int node, int par){ u[node] = 1; for(int i = 0; i < g[node].size(); i++) if(g[node][i] != par) { if(u[ g[node][i] ]){ b.pb(node); return g[node][i]; } int amk; amk = dfs(g[node][i], node); if(amk){ b.pb(node); if(amk == node) return 0; else return amk; } } return 0; } ii bul(int node, int par){ int mx = 0, say = 1, son = -1, top = 0, mx2 = 0; vector < ii > c; vector < int > pre; for(int i = 0; i < g[node].size(); i++) if(g[node][i] != par and !u[g[node][i]]){ ii don = bul(g[node][i], node); c.pb(mp(don.st + 1, don.nd)); pre.pb(0); } sort(c.begin(), c.end()); reverse(c.begin(), c.end()); for(int i = 0; i < c.size(); i++){ if(c[i].st == c[0].st){ pre[i] = ((i == 0)?0:pre[i-1]) + c[i].nd; son = i; }else if(c[i].st == c[son + 1].st){ top += c[i].nd; mx2 = c[i].st; } } if(son != -1){ mx = c[0].st, say = pre[son]; int sonmx = mx; int xx = say; yap(sonmx, xx); } if(son > 0){ int sonmx = c[0].st + c[0].st; int xx = 0; for(int i = 1; i <= son; i++) xx += pre[i - 1]*c[i].nd; yap(sonmx, xx); } if(son == 0){ int sonmx = c[0].st + mx2; int xx = (c[0].nd)*top; yap(sonmx, xx); } // cout << node << " -> " << mx << " , " << say << endl; return mp(mx, say); } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); scanf("%d",&n); for(int i = 1; i <= n; i++){ int u, v; scanf("%d %d",&u ,&v); g[u].pb(v); g[v].pb(u); } b.pb(0); dfs(1, 1); memset(u, 0, sizeof u); // for(int i = 1; i < b.size(); i++)cout << b[i] << " ";cout << endl; for(int i = 1; i < b.size(); i++)u[b[i]] = 1; for(int i = 1; i < b.size(); i++) c[++m] = bul(b[i], -1); for(int i = 1; i <= m; i++) for(int j = i + 1; j <= m; j++){ int sonmx = uz(i, j).st + c[i].st + c[j].st; int xx = uz(i, j).nd*c[i].nd*c[j].nd; yap(sonmx, xx); } printf("%d\n", kac); return 0; }

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

shymbulak.cpp: In function 'int dfs(int, int)':
shymbulak.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
shymbulak.cpp: In function 'ii bul(int, int)':
shymbulak.cpp:58:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
shymbulak.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < c.size(); i++){
                 ~~^~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:113:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < b.size(); i++)u[b[i]] = 1;
                 ~~^~~~~~~~~~
shymbulak.cpp:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < b.size(); i++)
                 ~~^~~~~~~~~~
shymbulak.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
shymbulak.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u ,&v);
   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...