제출 #902742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
902742		aqxa	Network (BOI15_net)	C++17	100 / 100	710 ms	127668 KiB

net

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
// works? 
struct graph {
    vector<vector<int>> adj;
    int n;
 
    graph() {} 
    graph(int _n) : n(_n) {
        adj.resize(n);
    }
 
    inline void add(int x, int y) {
        adj[x].push_back(y); 
        adj[y].push_back(x); 
    }
};
struct lca_graph : graph {
    using graph::adj;
    using graph::n; 
    vector<vector<int>> par; 
    vector<int> lev, path; 
    int lv = 0, lg; 
   	lca_graph(int _n) : graph(_n) {
        lg = __lg(n) + 1; 
        par = vector<vector<int>>(n, vector<int>(lg, -1)); 
        lev = vector<int>(n, 0); 
    }
    void make_lca(int x, int p) {
        path.push_back(x);
        lv++;
        lev[x] = lv;
 
        for (int i = 0; (1<<i) < path.size(); ++i) {
            par[x][i] = path[path.size()-1-(1<<i)];
        }
 
        for (auto u: adj[x]) {
            if (u != p) {
                make_lca(u, x);
            }
        }
        lv--;
        path.pop_back();
    }
    int ka(int u, int k) {
        if (k > lev[u] - 1) return 0; 
        while (k > 0) {
            int clg = (int) __lg(k);  
            k -= (1 << clg);
            u = par[u][clg];
        }
        return u;
    }
    int lca(int u, int v) {
        int du = lev[u], dv = lev[v];
        if (du < dv) {
            v = ka(v, dv - du);
            dv = du;
        } else if (du > dv) {
            u = ka(u, du - dv);
            du = dv;
        }
 
        if (u == v) return u;
 
        for (int i = lg-1; i >= 0; --i) {
            if (par[u][i] != par[v][i]) {
                u = par[u][i];  
                v = par[v][i];
				assert(u != -1 && v != -1);
            }
        }
		assert(u != -1); 
        return par[u][0];
    }
};
 
int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(0); 

// int tt; 
// cin >> tt;
// while (tt--) {
	int n; 
	cin >> n;
	lca_graph g(n); 
	for (int i = 0; i < n - 1; ++i) {
		int x, y; 
		cin >> x >> y; 
		g.add(--x, --y); 
	}
	vector<int> leafs; 
	set<int> leaf; 
	for (int i = 0; i < n; ++i) {
		if ((int) g.adj[i].size() == 1) {
			leaf.insert(i); 
			leafs.push_back(i); 
		}
	}
	for (int i = 0; i < n; ++i) {
		if (leaf.find(i) == leaf.end()) {
			g.make_lca(i, -1); 
			break; 
		}
	}
 
 	if ((int) leafs.size() % 2) {
		int x = leafs.back(); 
		for (int i = 0; i < n; ++i) {
			if (i != x && i != g.adj[x][0]) {
				leafs.push_back(i); 
				break; 
			}
		}
	}

	vector<pair<int, int>> ans; 
	
	for (int i = 0; i + 1 < (int) leafs.size(); i += 2) {
		if (!ans.size()) {
			ans.push_back(make_pair(leafs[i], leafs[i + 1])); 
			continue; 
		}
		auto p = ans.back(); 
		ans.pop_back(); 
		vector<int> v = {p.first, p.second, leafs[i], leafs[i + 1]}; 
		int best = 0; 
		pair<int, int> c = {2 * n, 2 * n}; 
		for (int f = 1; f < 4; ++f) {
			int a = g.lca(v[0], v[f]), b; 
			for (int j = 1; j < 4; ++j) {
				for (int k = j + 1; k < 4; ++k) {
					if (j != f && k != f) {
						b = g.lca(v[j], v[k]); 
						// cout << "Good\n";
					}
				}
			}
			a = g.lev[a]; 
			b = g.lev[b]; 
			if (a > b) swap(a, b); 
			pair<int, int> cur = {a, b}; 
			if (cur < c) {
				best = f; 
				c = cur; 
			}
		}
		ans.push_back({v[0], v[best]}); 
		for (int j = 1; j < 4; ++j) {
			for (int k = j + 1; k < 4; ++k) {
				if (j != best && k != best) {
					ans.push_back({v[j], v[k]}); 
				}
			}
		}
	}
 
	cout << (int) ans.size() << "\n";
	for (auto [x, y]: ans) {
		cout << x + 1 << " " << y + 1 << "\n";
	}
// }
 
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

net.cpp: In member function 'void lca_graph::make_lca(int, int)':
net.cpp:37:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int i = 0; (1<<i) < path.size(); ++i) {
      |                         ~~~~~~~^~~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:145:15: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  145 |    b = g.lev[b];
      |               ^

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