Submission #1173399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173399		InvMOD	Network (BOI15_net)	C++20	0 / 100	0 ms	324 KiB

net

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

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REV(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 2e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;


void solve()
{
    int n; cin >> n;

    vector<vector<int>> adj(n + 1, vector<int>());
    for(int i = 1; i < n; i++){
        int u,v; cin >> u >> v;
        adj[u].pb(v), adj[v].pb(u);
    }

    vector<int> dp(n + 1, 0);

    function<void(int,int)> dfs = [&](int x, int p) -> void{
        if(sz(adj[x]) == 1) dp[x] = 1;

        for(int v : adj[x])if(v != p){
            dfs(v, x);
            dp[x] += dp[v];
        }

        return;
    };

    vector<int> MnLeaf(n + 1, n + 1);
    function<void(int,int)> find_opt = [&](int x, int p) -> void{
        for(int v : adj[x])if(v != p){
            MnLeaf[v] = min(MnLeaf[v], dp[x] - dp[v]);
            find_opt(v, x);
        }

        for(int v : adj[x])if(v != p){
            MnLeaf[x] = min(MnLeaf[x], dp[v]);
        }
        return;
    };
    dfs(1, -1); find_opt(1, -1);

    int optLeaf = 0;
    for(int i = 1; i <= n; i++){
        if(MnLeaf[optLeaf] > MnLeaf[i]){
            optLeaf = i;
        }
    }

    vector<pair<int,int>> oper; stack<int> save; stack<int> node;


    function<void(int,int)> calc_op = [&](int x, int p) -> void{
        if(sz(adj[x]) == 1){
            if(sz(node)){
                oper.push_back(make_pair(node.top(), x));
                node.pop();
            }
            else{
                if(x == optLeaf){
                    node.push(x);
                }
                else save.push(x);
            }
        }

        for(int v : adj[x])if(v != p){
            calc_op(v, x);

            if(x == optLeaf){
                while(sz(save)){
                    node.push(save.top());
                    save.pop();
                }
            }
        }
    };

    calc_op(1, -1);
    assert(sz(node) <= 1);

    if(sz(node)){
        oper.push_back(make_pair(node.top(), optLeaf));
        node.pop();
    }

    cout << sz(oper) << "\n";
    for(int i = 0; i < sz(oper); i++){
        cout << oper[i].first <<" " << oper[i].second << "\n";
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
net.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37