Submission #666746

#TimeUsernameProblemLanguageResultExecution timeMemory
666746KalashnikovHard route (IZhO17_road)C++17
0 / 100
7 ms12072 KiB
#include <bits/stdc++.h> #define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) #define all(a) a.begin() , a.end() #define F first #define S second using namespace std; using ll = long long; const int N = 5e5+5 , inf = 2e9 + 7; const ll INF = 1e18 , mod = 1e9+7 , P = 6547; int a[N]; vector<int> g[N]; pair<int,int> diam(int v, int dep = 0, int p = 0) { pair<int,int> res = {dep , v}; for(auto to: g[v]) { if(to != p) { res = max(res, diam(to , dep+1 , v)); } } return res; } void getw(int v, int fn, vector<int> &dw , int p = 0) { if(v == fn) { dw.push_back(v); return; } for(auto to: g[v]) { if(to != p) { getw(to, fn, dw , v); if(dw.size()) { dw.push_back(v); return; } } } } void solve(int tc) { int n; cin >> n; for(int i = 1; i < n; i ++) { int a , b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } int ans = 0 , cans = 1; for(int i = 1; i <= n; i ++) { vector<int> vec; for(auto to: g[i]) { vec.push_back(diam(to,0,i).F+1); } sort(all(vec)); for(int j = 0; j < vec.size(); j ++) { for(int k = 0; k < vec.size(); k ++) { if(j == k) continue; for(int t = k+1; t < vec.size(); t ++) { if(t == j || t == k) continue; int res = vec[j]*(vec[k]+vec[t]); if(res == ans) cans ++; if(res > ans) { ans = res; cans = 1; } } } } } cout << ans << ' ' << cans << '\n'; } /* */ main() { ios; int tt = 1 , tc = 0; // cin >> tt; while(tt --) { solve(++tc); } return 0; }

Compilation message (stderr)

road.cpp: In function 'void solve(int)':
road.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int j = 0; j < vec.size(); j ++) {
      |                  ~~^~~~~~~~~~~~
road.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |    for(int k = 0; k < vec.size(); k ++) {
      |                   ~~^~~~~~~~~~~~
road.cpp:63:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int t = k+1; t < vec.size(); t ++) {
      |                      ~~^~~~~~~~~~~~
road.cpp: At global scope:
road.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...