oj.uz

Submission #1051039

# Submission time Handle Problem Language Result Execution time Memory
1051039 2024-08-09T18:43:01 Z Ahmed57 Hard route (IZhO17_road) C++17
52 / 100
 4 ms 8028 KB 
#include "bits/stdc++.h"

using namespace std;
vector<int> adj[100001];
int mx[100001];
int cnt[100001];
pair<int,int> pref[100001];
long long overMA = 0;
long long overCNT = 1;
void dfs(int i,int pr){
    mx[i] = 0 , cnt[i] = 1;
    for(auto j:adj[i]){
        if(j==pr)continue;
        dfs(j,i);
        if(mx[j]+1>mx[i]){
            mx[i] = mx[j]+1;
            cnt[i] = 0;
        }
        if(mx[j]+1==mx[i]){
            cnt[i]+=cnt[j];
        }
    }
}
void reroot(int i,int pr,int MA,int CNT){
    vector<pair<int,int>> v;
    if(MA)v.push_back({MA,CNT});
    for(auto j:adj[i]){
        if(j==pr)continue;
        v.push_back({mx[j]+1,cnt[j]});
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    if(v.size()>=3){
        int z = v[0].first , y = v[1].first , x = v[2].first;
        long long cost = 0;
        if(x<y&&y<z){
            int A = v[0].second , B = v[1].second , C = v[2].second;
            for(int i = 3;i<v.size();i++)if(v[i].first==x)C+=v[i].second;
            cost = B*C;
        }else if(x<y&&y==z){
            int A = v[0].second , B = v[1].second , C = v[2].second;
            for(int i = 3;i<v.size();i++)if(v[i].first==x)C+=v[i].second;
            cost = (A+B)*C;
        }else if(x==y&&y<z){
            int A = v[0].second , B = v[1].second , C = v[2].second;
            cost = B*C;
            long long sum = B+C;
            for(int i = 3;i<v.size();i++){
                if(v[i].first==x){
                    cost+=sum*v[i].second;
                    sum+=v[i].second;
                }
            }
        }else if(x==y&&y==z){
            int A = v[0].second , B = v[1].second , C = v[2].second;
            cost = A*B+(A+B)*C;
            long long sum = A+B+C;
            for(int i = 3;i<v.size();i++){
                if(v[i].first==x){
                    cost+=sum*v[i].second;
                    sum+=v[i].second;
                }
            }
        }
        if(overMA<(x+y)*z){
            overMA = (x+y)*z;
            overCNT = 0;
        }
        if(overMA==(x+y)*z){
            overCNT+=cost;
        }
    }
    pair<int,int> cur = {MA,CNT};
    for(auto j:adj[i]){
        if(j==pr)continue;
        pref[j] = cur;
        if(mx[j]+1>cur.first){
            cur.first = mx[j]+1;
            cur.second = 0;
        }
        if(mx[j]+1==cur.first){
            cur.second+=cnt[j];
        }
    }
    reverse(adj[i].begin(),adj[i].end());
    cur = {-1e9,0};
    for(auto j:adj[i]){
        if(j==pr)continue;
        if(cur.first>pref[j].first)pref[j] = cur;
        else if(cur.first==pref[j].first)pref[j].second+=cur.second;
        if(mx[j]+1>cur.first){
            cur.first = mx[j]+1;
            cur.second = 0;
        }
        if(mx[j]+1==cur.first){
            cur.second+=cnt[j];
        }
    }
    reverse(adj[i].begin(),adj[i].end());
    for(auto j:adj[i]){
        if(j==pr)continue;
        reroot(j,i,pref[j].first+1,pref[j].second);
    }
}
int main(){
    int n;
    cin>>n;
    for(int i = 1;i<n;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1,0);
    reroot(1,0,0,1);
    cout<<overMA<<" "<<overCNT<<endl;
}

Compilation message

road.cpp: In function 'void reroot(int, int, int, int)':
road.cpp:38:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             for(int i = 3;i<v.size();i++)if(v[i].first==x)C+=v[i].second;
      |                           ~^~~~~~~~~
road.cpp:37:17: warning: unused variable 'A' [-Wunused-variable]
   37 |             int A = v[0].second , B = v[1].second , C = v[2].second;
      |                 ^
road.cpp:42:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             for(int i = 3;i<v.size();i++)if(v[i].first==x)C+=v[i].second;
      |                           ~^~~~~~~~~
road.cpp:48:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             for(int i = 3;i<v.size();i++){
      |                           ~^~~~~~~~~
road.cpp:45:17: warning: unused variable 'A' [-Wunused-variable]
   45 |             int A = v[0].second , B = v[1].second , C = v[2].second;
      |                 ^
road.cpp:58:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for(int i = 3;i<v.size();i++){
      |                           ~^~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 1 ms 3932 KB Output is correct
8 Correct 1 ms 3968 KB Output is correct
9 Correct 1 ms 3932 KB Output is correct
10 Correct 1 ms 4188 KB Output is correct
11 Correct 1 ms 4188 KB Output is correct
12 Correct 1 ms 4188 KB Output is correct
13 Correct 1 ms 4188 KB Output is correct
14 Correct 1 ms 4188 KB Output is correct
15 Correct 1 ms 4184 KB Output is correct
16 Correct 1 ms 4188 KB Output is correct
17 Correct 1 ms 4188 KB Output is correct
18 Correct 1 ms 4188 KB Output is correct
19 Correct 1 ms 4188 KB Output is correct
20 Correct 1 ms 4188 KB Output is correct
21 Correct 1 ms 4188 KB Output is correct
22 Correct 1 ms 3932 KB Output is correct
23 Correct 1 ms 4032 KB Output is correct
24 Correct 1 ms 4188 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 1 ms 3932 KB Output is correct
8 Correct 1 ms 3968 KB Output is correct
9 Correct 1 ms 3932 KB Output is correct
10 Correct 1 ms 4188 KB Output is correct
11 Correct 1 ms 4188 KB Output is correct
12 Correct 1 ms 4188 KB Output is correct
13 Correct 1 ms 4188 KB Output is correct
14 Correct 1 ms 4188 KB Output is correct
15 Correct 1 ms 4184 KB Output is correct
16 Correct 1 ms 4188 KB Output is correct
17 Correct 1 ms 4188 KB Output is correct
18 Correct 1 ms 4188 KB Output is correct
19 Correct 1 ms 4188 KB Output is correct
20 Correct 1 ms 4188 KB Output is correct
21 Correct 1 ms 4188 KB Output is correct
22 Correct 1 ms 3932 KB Output is correct
23 Correct 1 ms 4032 KB Output is correct
24 Correct 1 ms 4188 KB Output is correct
25 Correct 3 ms 4444 KB Output is correct
26 Correct 4 ms 4696 KB Output is correct
27 Correct 4 ms 4700 KB Output is correct
28 Correct 3 ms 4700 KB Output is correct
29 Correct 3 ms 4700 KB Output is correct
30 Correct 3 ms 4616 KB Output is correct
31 Correct 3 ms 4700 KB Output is correct
32 Correct 3 ms 4700 KB Output is correct
33 Correct 3 ms 4700 KB Output is correct
34 Correct 3 ms 4768 KB Output is correct
35 Correct 3 ms 4796 KB Output is correct
36 Correct 3 ms 4700 KB Output is correct
37 Correct 4 ms 4952 KB Output is correct
38 Correct 3 ms 5312 KB Output is correct
39 Correct 3 ms 4696 KB Output is correct
40 Correct 3 ms 4444 KB Output is correct
41 Correct 3 ms 4444 KB Output is correct
42 Correct 3 ms 4312 KB Output is correct
43 Correct 3 ms 4188 KB Output is correct
44 Correct 3 ms 4188 KB Output is correct
45 Correct 3 ms 4188 KB Output is correct
46 Correct 2 ms 4188 KB Output is correct
47 Correct 2 ms 4444 KB Output is correct
48 Correct 3 ms 4404 KB Output is correct

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 1 ms 3932 KB Output is correct
8 Correct 1 ms 3968 KB Output is correct
9 Correct 1 ms 3932 KB Output is correct
10 Correct 1 ms 4188 KB Output is correct
11 Correct 1 ms 4188 KB Output is correct
12 Correct 1 ms 4188 KB Output is correct
13 Correct 1 ms 4188 KB Output is correct
14 Correct 1 ms 4188 KB Output is correct
15 Correct 1 ms 4184 KB Output is correct
16 Correct 1 ms 4188 KB Output is correct
17 Correct 1 ms 4188 KB Output is correct
18 Correct 1 ms 4188 KB Output is correct
19 Correct 1 ms 4188 KB Output is correct
20 Correct 1 ms 4188 KB Output is correct
21 Correct 1 ms 4188 KB Output is correct
22 Correct 1 ms 3932 KB Output is correct
23 Correct 1 ms 4032 KB Output is correct
24 Correct 1 ms 4188 KB Output is correct
25 Correct 3 ms 4444 KB Output is correct
26 Correct 4 ms 4696 KB Output is correct
27 Correct 4 ms 4700 KB Output is correct
28 Correct 3 ms 4700 KB Output is correct
29 Correct 3 ms 4700 KB Output is correct
30 Correct 3 ms 4616 KB Output is correct
31 Correct 3 ms 4700 KB Output is correct
32 Correct 3 ms 4700 KB Output is correct
33 Correct 3 ms 4700 KB Output is correct
34 Correct 3 ms 4768 KB Output is correct
35 Correct 3 ms 4796 KB Output is correct
36 Correct 3 ms 4700 KB Output is correct
37 Correct 4 ms 4952 KB Output is correct
38 Correct 3 ms 5312 KB Output is correct
39 Correct 3 ms 4696 KB Output is correct
40 Correct 3 ms 4444 KB Output is correct
41 Correct 3 ms 4444 KB Output is correct
42 Correct 3 ms 4312 KB Output is correct
43 Correct 3 ms 4188 KB Output is correct
44 Correct 3 ms 4188 KB Output is correct
45 Correct 3 ms 4188 KB Output is correct
46 Correct 2 ms 4188 KB Output is correct
47 Correct 2 ms 4444 KB Output is correct
48 Correct 3 ms 4404 KB Output is correct
49 Runtime error 3 ms 8028 KB Execution killed with signal 11
50 Halted 0 ms 0 KB -