Submission #855485

#	Time	Username	Problem	Language	Result	Execution time	Memory
855485		Alfraganus	Hard route (IZhO17_road)	C++17	19 / 100	2058 ms	860 KiB

road

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ll long long
#define fs first
#define ss second
#define all(a) a.begin(), a.end()
#define print(a)          \
    for (auto x : a)      \
        cout << x << ' '; \
    cout << endl;

#define printmp(a)   \
    for (auto x : a) \
        cout << x.fs << ' ' << x.ss << endl;

vector<vector<int>> graph;
vector<int> termials, path;
vector<bool> used;
queue<pair<int, int>> q;

bool dfs1(int node, int target){
    if(node == target)
        return true;
    for(auto neighbour : graph[node]){
        if(!used[neighbour]){
            used[neighbour] = 1;
            if(dfs1(neighbour, target)){
                q.push({neighbour, 0});
                path.push_back(neighbour);
                return true;
            }
        }
    }
    return false;
}

void solve()
{
    int n;
    cin >> n;
    graph.resize(n + 1);
    used.resize(n + 1);
    for(int i = 0; i < n - 1; i ++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i = 1; i <= n; i ++)
        if(graph[i].size() == 1)
            termials.push_back(i);
    int ans1 = 0, ans2 = 0;
    for(int i = 0; i < termials.size(); i ++){
        for(int j = i + 1; j < termials.size(); j ++){
            used.clear();
            used.resize(n + 1);
            path.clear();
            path.push_back(termials[i]);
            q.push({termials[i], 0});
            dfs1(termials[i], termials[j]);
            used.clear();
            used.resize(n + 1);
            for (auto x : path)
                used[x] = 1;
            int mx = 0;
            while (!q.empty())
            {
                pair<int, int> x = q.front();
                q.pop();
                mx = max(mx, x.ss);

                for (auto neighbour : graph[x.fs])
                {
                    if (!used[neighbour])
                    {
                        used[neighbour] = 1;
                        q.push({neighbour, x.ss + 1});
                    }
                }
            }
            if (ans1 < (path.size() - 1) * mx)
                ans1 = (path.size() - 1) * mx, ans2 = 1;
            else if (ans1 == (path.size() - 1) * mx)
                ans2++;
        }
    }
    cout << ans1 << ' ' << ans2 << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
}

Compilation message (stderr)

road.cpp: In function 'void solve()':
road.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i = 0; i < termials.size(); i ++){
      |                    ~~^~~~~~~~~~~~~~~~~
road.cpp:56:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int j = i + 1; j < termials.size(); j ++){
      |                            ~~^~~~~~~~~~~~~~~~~
road.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             if (ans1 < (path.size() - 1) * mx)
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
road.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             else if (ans1 == (path.size() - 1) * mx)
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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