Submission #758209

#	Time	Username	Problem	Language	Result	Execution time	Memory
758209		vjudge1	Hard route (IZhO17_road)	C++17	19 / 100	6 ms	468 KiB

road

#include <bits/stdc++.h>
#include <fstream>
#define endl '\n'
#define mod 1000007
#define INF 1000000000000000000
//#define ll long long
///#define cin fin
///#define cout fout
#define fi first
#define se second
using namespace std;
double const EPS = 1e-14;
///ofstream fout("herding.out");
///ifstream fin("herding.in");
const int Max = 100 + 5;
vector<int> v[Max];
bool mark[Max], mark2[Max]; vector<int> ter, order;
int start; int path, path2, path3, path4;
pair<int,int> ans;

void dfs2(int s, int p) {
    path2 = max(path2,path3);
    for(auto i : v[s]) {
        if(i != p && mark2[i] == 0) {
            path3++;
            dfs2(i,s);
            path3--;
        }
    }
}

void dfs(int s, int p) {
    order.push_back(s);
    mark2[s] = 1;
    if(mark[s] == 1 && s != start) {
        path4 = 0;
        for(int i = 0; i < order.size(); i++) {
            path2 = 0;
            dfs2(order[i],0);
            path4 = max(path4,path2);

        }
        if(ans.first < path*path4) {
            ans.first = path*path4;
            ans.second = 1;
        } else if(ans.first == path*path4) {
            ans.second++;
        }
    }
    for(auto i : v[s]) {
        if(i != p) {
            path++;
            dfs(i,s);
            path--;
        }
    }
    order.pop_back();
    mark2[s] = 0;
}

int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int n; cin >> n; ans.second = 1;
    for(int i = 0; i < n-1 ; i++) {
        int a, b; cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i = 1; i <= n; i++) {
        if(v[i].size() == 1) {
            mark[i] = 1;
            ter.push_back(i);
        }
    }
    for(int i = 0; i < ter.size(); i++) {
        start = ter[i];
        dfs(ter[i],0);
    }
    cout << ans.first << ' ' << ans.second/2;
 return 0;
}

Compilation message (stderr)

road.cpp: In function 'void dfs(int, int)':
road.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int i = 0; i < order.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~
road.cpp: In function 'int main()':
road.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0; i < ter.size(); i++) {
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 0 / 33
• Subtask 3: 0 / 48