Submission #1096649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096649		raphaelp	Infiltration (CCO24_day2problem1)	C++14	25 / 25	11 ms	1628 KiB

Main

#include <bits/stdc++.h>
using namespace std;
pair<int, int> dfs(int x, int p, vector<vector<int>> &AR, int depth)
{
    pair<int, int> ans = {depth, x};
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i] == p)
            continue;
        ans = min(ans, dfs(AR[x][i], x, AR, depth + 1));
    }
    return ans;
}
pair<int, int> dfs2(int x, int p, vector<vector<int>> &AR, int depth)
{
    pair<int, int> ans = {depth / 2, -1};
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i] == p)
            continue;
        pair<int, int> temp = dfs2(AR[x][i], x, AR, depth + 1);
        if (temp.second != -1 && (ans.second == -1 || ans.first < temp.first))
            ans = temp;
        if (ans.second == -1 && temp.first > ans.first)
            ans = temp;
    }
    if (ans.second == -1 && depth == ans.first)
        ans = {depth, x};
    return ans;
}
void dfs3(int x, int p, vector<vector<int>> &AR, vector<int> &par)
{
    par[x] = p;
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i] == p)
            continue;
        dfs3(AR[x][i], x, AR, par);
    }
}
int main()
{
    int N;
    cin >> N;
    if (N != 100)
        return 0;
    vector<vector<int>> AR(N);
    for (int i = 0; i < N - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        AR[a].push_back(b);
        AR[b].push_back(a);
    }
    pair<int, int> far = dfs(0, 0, AR, 0);
    pair<int, int> centre = dfs2(far.second, far.second, AR, 1);
    int mil = centre.second;
    vector<int> p(N);
    dfs3(mil, mil, AR, p);
    vector<vector<int>> ans1(N), ans2(N);
    for (int i = 0; i < N; i++)
    {
        ans1[i].push_back(i);
        ans2[i].push_back(i);
    }
    vector<int> dist = {3, -12, 27, -56, 88, -100};
    for (int i = 0; i < dist.size(); i++)
    {
        if (dist[i] > 0)
        {
            for (int j = 0; j < dist[i]; j++)
            {
                int stop = 1;
                for (int k = 0; k < N; k++)
                {
                    ans2[k].push_back(ans2[k][ans2[k].size() - 1]);
                    ans1[k].push_back(p[ans1[k][ans1[k].size() - 1]]);
                    if (ans1[k][ans1[k].size() - 1] != mil)
                        stop = 0;
                }
                for (int k = 0; k < N; k++)
                {
                    ans2[k].push_back(ans2[k][ans2[k].size() - 1]);
                    ans1[k].push_back(ans1[k][ans1[k].size() - 1]);
                }
                // if (stop)
                //  break;
            }
        }
        else
        {
            for (int j = 0; j < -dist[i]; j++)
            {
                int stop = 1;
                for (int k = 0; k < N; k++)
                {
                    ans2[k].push_back(ans2[k][ans2[k].size() - 1]);
                    ans1[k].push_back(ans1[k][ans1[k].size() - 1]);
                }
                for (int k = 0; k < N; k++)
                {
                    ans2[k].push_back(p[ans2[k][ans2[k].size() - 1]]);
                    ans1[k].push_back(ans1[k][ans1[k].size() - 1]);
                    if (ans2[k][ans2[k].size() - 1] != mil)
                        stop = 0;
                }
                // if (stop)
                // break;
            }
        }
    }
    cout << ans1[0].size() - 1 << endl;
    for (int i = 0; i < N; i++)
    {
        for (int j = 1; j < ans1[0].size() - 1; j++)
        {
            cout << ans1[i][j] << ' ';
        }
        cout << ans1[i][ans1[i].size() - 1] << '\n';
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 1; j < ans2[0].size() - 1; j++)
        {
            cout << ans2[i][j] << ' ';
        }
        cout << ans2[i][ans2[i].size() - 1] << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'std::pair<int, int> dfs(int, int, std::vector<std::vector<int> >&, int)':
Main.cpp:6:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
Main.cpp: In function 'std::pair<int, int> dfs2(int, int, std::vector<std::vector<int> >&, int)':
Main.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
Main.cpp: In function 'void dfs3(int, int, std::vector<std::vector<int> >&, std::vector<int>&)':
Main.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < dist.size(); i++)
      |                     ~~^~~~~~~~~~~~~
Main.cpp:73:21: warning: variable 'stop' set but not used [-Wunused-but-set-variable]
   73 |                 int stop = 1;
      |                     ^~~~
Main.cpp:94:21: warning: variable 'stop' set but not used [-Wunused-but-set-variable]
   94 |                 int stop = 1;
      |                     ^~~~
Main.cpp:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for (int j = 1; j < ans1[0].size() - 1; j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:123:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (int j = 1; j < ans2[0].size() - 1; j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25