oj.uz

Submission #855485

# Submission time Handle Problem Language Result Execution time Memory
855485 2023-10-01T10:24:41 Z Alfraganus Hard route (IZhO17_road) C++17
19 / 100
 2000 ms 860 KB 
#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

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 7 ms 460 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 7 ms 460 KB Output is correct
25 Execution timed out 2058 ms 860 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 7 ms 460 KB Output is correct
25 Execution timed out 2058 ms 860 KB Time limit exceeded
26 Halted 0 ms 0 KB -