DFS#11793
Увійти

DFS (Розбір)

Problem Author:

Illia Shevchenko

Prepared by:

Illia Shevchenko, Maksym Shvedchenko

Editorial by:

Maksym Shvedchenko

We will solve the problem in reverse: first, we construct a dfs tree such that \sum_{v=1}^{n} \operatorname{deg}_v^2 is maximized, and we can add m - (n - 1) edges to the tree without changing the DFS traversal. It can be shown that the maximum number of such edges is bounded by \sum_{v=1}^{n} \operatorname{depth}_v, where \operatorname{depth}_v represents the distance from vertex to the root.

Our answer (resulting dfs tree) can always be represented as follows:

That is, first a bamboo (a straight path), with a star at the end.

That is, the only thing left is to determine the size of the "star." This can be done either using binary search or simply by traversing the structure.

#pragma gcc optimize "Ofast"
 
///In honor of TimDee
 
/*
I want earrings with minecreaft
I want earrings with birbie
*/
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <string>
#include <queue>
#include <random>
#include <chrono>
#include <unordered_map>
 
 
using namespace std;
 
#define int long long
 
int inf = 1000000007000000007ll;
int NADIYA = 40;
int mod = 1000000007;
int log_ = 20;
 
int p = 501;
 
 
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
 
    int n, m, c;
    cin >> n >> m >> c;
 
    int ans = 0;
 
    int s_ = 0;
 
    for (int s = 1; s <= n - 1; s++)
    {
        int col = (n*(n - 1))/2 - ((n - s - 1)* (n - s - 2))/2;
 
        if (col >= m)
        {
            int x = 0;
 
            x += (n - s) * (n - s);
 
            x += n - s;
 
            x += (s - 1) * 4;
 
            if (ans < x)
            {
                ans = x;
                s_ = s;
            }
        }
    }
 
 
    if (c == 1)
    {
        cout << ans;
    }
    else
    {
        cout << ans << "\n";
 
        int col = 0;
        for (int i = 0; i < s_; i++)
        {
            col++;
            cout << i + 1 << " " << i + 2 << "\n";
        }
 
        int p = s_;
 
        for (int i = s_+1; i < n; i++)
        {
            cout << p + 1 << " " << i + 1 << "\n";
            col++;
        }
 
        for (int i = 0; i < p; i++)
        {
            for (int j = i+2; j < n; j++)
            {
                if (col == m)
                    break;
                
                col++;
                cout << i + 1 << " " << j + 1 << "\n";
            }
 
            if (col == m)
                break;
        }
    }
}
C++