oj.uz

Submission #696575

# Submission time Handle Problem Language Result Execution time Memory
696575 2023-02-06T23:23:48 Z bane Hard route (IZhO17_road) C++17
0 / 100
 12 ms 16780 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<deque>
#include<map>
#include<set>
#include<unordered_set>
using namespace std;
 
#ifdef LOCAL
    #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
    #define eprintf(...) 42
#endif
 
#define pb push_back
#define mp make_pair
#define ins insert
#define popb pop_back
#define popf pop_front
#define ft front
#define bk back
#define fr first
#define sc second
using ll = long long;
using ld = long double;
using db = double;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<ld,ld>;
using str = string;
vector<int>jokeri[200005];
const int NAX = (int)1e5 + 1;
const int MOD = (int)1e9 + 7;
vector<int>adj[500001];
int f[500001], h[500001], g[500001];
int n;
int best = 0;
int ways = 0;

void upd(int b, int w){
    if (b == best)ways+=w;
    else if (b > best){
        best = b;
        ways = w;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i + 1 < n; i++){
        int a,b;
        cin >> a >> b;
        adj[a].pb(b);adj[b].pb(a);
    }
    function<void(int,int)>internal = [&](int u, int p){
        static_cast<void>(f[u] = 0), static_cast<void>(h[u] = 0), g[u] = 0;
        for (int& x : adj[u]){
            if (x == p)continue;
            internal(x, u);
            if (f[x] + 1 > f[u]){
                h[u] = f[u];
                f[u] = f[x] + 1;
            }else h[u] = max(h[u], f[x] + 1);
            
        }
    };
    internal(1,1);
    function<void(int,int)>external = [&](int u, int p){
        for (int& x : adj[u]){
            if (x == p)continue;
          //  cout<<x<<" "<<g[u]<<endl;
            if (f[x] == f[u] - 1){
                g[x] = max(g[u] + 1, h[u] + 1);
            }else{
                g[x] = max(g[u] + 1, f[u] + 1);
            }
            external(x, u);
        }
    };
   // cout<<g[4];
    external(1,1);
    function<void(int, int)>dfs =[&](int u, int p){
        vector<int>temp;
      //  if(u != 1)temp.pb(g[u]);
        for (int i = 0; i < adj[u].size(); i++){
            if (adj[u][i] == p)continue;
            temp.pb(f[adj[u][i]]);
        }
        sort(temp.rbegin(), temp.rend());
       // cout<<u<<" "<<f[u]<<" "<<g[u]<<'\n';
        for (int i = 2; i<temp.size(); i++){
            int case1 = (temp[i] + 1)* (temp[i - 1] + temp[i - 2] + 2);
            int case2 = (temp[i-1] + 1)* (temp[i] + temp[i - 2] + 2);
            int case3 = (temp[i - 2] + 1)* (temp[i] + temp[i - 1] + 2);
            upd(case1, 1);
            upd(case2, 1);
            upd(case3, 1);
        }
        
        if (u != 1)
        for (int i = 1; i<temp.size(); i++){
            int case1 = (g[u]) * (temp[i] + temp[i - 1] + 2);
            int case2 = (temp[i] + 1) * (temp[i-1] + g[u] + 1);
            int case3 = (temp[i - 1] + 1) * (temp[i] + g[u] + 1);
            upd(case1,1);
            upd(case2,1);
            upd(case3,1);
        }
        for (int& x : adj[u]){
            if (x == p)continue;
            dfs(x,u);
        }
    };
    dfs(1,1);
    cout<<best<<' '<<ways + (best == 0);
    return 0;
}

Compilation message

road.cpp: In lambda function:
road.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int i = 0; i < adj[u].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~
road.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for (int i = 2; i<temp.size(); i++){
      |                         ~^~~~~~~~~~~~
road.cpp:105:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for (int i = 1; i<temp.size(); i++){
      |                         ~^~~~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 12 ms 16780 KB Output is correct
3 Correct 8 ms 16724 KB Output is correct
4 Correct 10 ms 16724 KB Output is correct
5 Correct 8 ms 16768 KB Output is correct
6 Correct 8 ms 16724 KB Output is correct
7 Incorrect 8 ms 16764 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 12 ms 16780 KB Output is correct
3 Correct 8 ms 16724 KB Output is correct
4 Correct 10 ms 16724 KB Output is correct
5 Correct 8 ms 16768 KB Output is correct
6 Correct 8 ms 16724 KB Output is correct
7 Incorrect 8 ms 16764 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 12 ms 16780 KB Output is correct
3 Correct 8 ms 16724 KB Output is correct
4 Correct 10 ms 16724 KB Output is correct
5 Correct 8 ms 16768 KB Output is correct
6 Correct 8 ms 16724 KB Output is correct
7 Incorrect 8 ms 16764 KB Output isn't correct
8 Halted 0 ms 0 KB -