結果
| 問題 | No.3405 Engineering University of Tree |
| コンテスト | |
| ユーザー |
 umimel
|
| 提出日時 | 2025-12-12 12:10:18 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 829 ms / 2,000 ms |
| コード長 | 9,657 bytes |
| 記録 | |
| コンパイル時間 | 3,045 ms |
| コンパイル使用メモリ | 208,652 KB |
| 実行使用メモリ | 109,760 KB |
| 最終ジャッジ日時 | 2025-12-12 12:10:36 |
| 合計ジャッジ時間 | 15,391 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 21 |
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:269:18: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
269 | for(auto [d, v] : sdeg){
| ^
ソースコード
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define fi first
#define se second
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const ll MOD1000000007 = 1000000007;
const ll MOD998244353 = 998244353;
const ll MOD[3] = {999727999, 1070777777, 1000000007};
const ll LINF = 1LL << 60LL;
const int IINF = (1 << 30) - 1;
template<typename T>
struct edge{
int from;
int to;
T cost;
int id;
edge(){}
edge(int to, T cost=1) : from(-1), to(to), cost(cost){}
edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id){}
void reverse(){swap(from, to);}
};
template<typename T>
struct edges : std::vector<edge<T>>{
void sort(){
std::sort(
(*this).begin(),
(*this).end(),
[](const edge<T>& a, const edge<T>& b){
return a.cost < b.cost;
}
);
}
};
template<typename T = bool>
struct graph : std::vector<edges<T>>{
private:
int n = 0;
int m = 0;
edges<T> es;
bool dir;
public:
graph(int n, bool dir) : n(n), dir(dir){
(*this).resize(n);
}
void add_edge(int from, int to, T cost=1){
if(dir){
es.push_back(edge<T>(from, to, cost, m));
(*this)[from].push_back(edge<T>(from, to, cost, m++));
}else{
if(from > to) swap(from, to);
es.push_back(edge<T>(from, to, cost, m));
(*this)[from].push_back(edge<T>(from, to, cost, m));
(*this)[to].push_back(edge<T>(to, from, cost, m++));
}
}
int get_vnum(){
return n;
}
int get_enum(){
return m;
}
bool get_dir(){
return dir;
}
edge<T> get_edge(int i){
return es[i];
}
edges<T> get_edge_set(){
return es;
}
};
template<typename T>
struct redge{
int from, to;
T cap, cost;
int rev;
redge(int to, T cap, T cost=(T)(1)) : from(-1), to(to), cap(cap), cost(cost){}
redge(int to, T cap, T cost, int rev) : from(-1), to(to), cap(cap), cost(cost), rev(rev){}
};
template<typename T> using Edges = vector<edge<T>>;
template<typename T> using weighted_graph = vector<Edges<T>>;
template<typename T> using tree = vector<Edges<T>>;
using unweighted_graph = vector<vector<int>>;
template<typename T> using residual_graph = vector<vector<redge<T>>>;
template<typename W>
struct lowest_common_ancestor{
int root = 0;
int n;
int log_n = 1;
vector<vector<int>> par;
vector<int> depth;
lowest_common_ancestor(){}
lowest_common_ancestor(tree<W> &T, int root=0) : root(root){
n = (int)T.size();
while((1 << log_n) < n) log_n++;
par.resize(log_n, vector<int>(n, -1));
depth.resize(n, 0);
init(T);
}
void init(tree<W> &T){
function<void(int, int)> dfs = [&](int v, int p){
par[0][v] = p;
for(edge<W> e : T[v]) if(e.to!=p){
depth[e.to] = depth[v]+1;
dfs(e.to, v);
}
};
dfs(root, -1);
for(int k=0; k+1<log_n; k++){
for(int v=0; v<n; v++){
if(par[k][v]<0) par[k+1][v] = -1;
else par[k+1][v] = par[k][par[k][v]];
}
}
}
int query(int u, int v){
if(depth[u] < depth[v]) swap(u, v);
for(int k=0; k<log_n; k++) if((depth[u]-depth[v]) >> k & 1) u = par[k][u];
if(u == v) return u;
for(int k=log_n-1; k>=0; k--){
if(par[k][u] != par[k][v]){
u = par[k][u];
v = par[k][v];
}
}
return par[0][u];
}
};
template<typename W>
struct auxiliary_tree{
int n;
vector<int> in;
int root;
lowest_common_ancestor<W> lca;
auxiliary_tree(tree<W> &T, int root = 0) : root(root){
n = (int)T.size();
in.resize(n);
euler_tour(T);
lca = lowest_common_ancestor<W>(T, root);
}
void euler_tour(tree<W> &T){
int now = 0;
function<void(int, int)> dfs = [&](int v, int p){
in[v] = now++;
for(edge<W> e : T[v]) if(e.to != p) dfs(e.to, v);
}; dfs(root, -1);
}
int build(int k, vector<int> &vs, tree<W> &AT){
sort(vs.begin(), vs.end(), [&](int i, int j){return in[i] < in[j];});
stack<int> stk;
stk.push(vs[0]);
AT[vs[0]] = {};
for(int i=0; i<k-1; i++){
int r = lca.query(vs[i], vs[i+1]);
if(r != vs[i]){
int last = stk.top();
stk.pop();
while(!stk.empty()&&lca.depth[r]<lca.depth[stk.top()]){
AT[stk.top()].push_back(edge<W>(last));
last = stk.top();
stk.pop();
}
if(stk.empty()||stk.top()!=r){
stk.push(r);
vs.push_back(r);
AT[r] = {edge<W>(last)};
}else{
AT[r].push_back(edge<W>(last));
}
}
stk.push(vs[i+1]);
AT[vs[i+1]] = {};
}
int r = stk.top();
while(!stk.empty()){
stk.pop();
if(!stk.empty()){
AT[stk.top()].push_back(edge<W>(r));
r = stk.top();
}
}
function<void(int, int)> dfs = [&](int v, int p){
for(edge<int> e : AT[v]) if(e.to != p){
AT[e.to].push_back(edge<int>(v));
dfs(e.to, v);
}
}; dfs(r, -1);
return r;
}
};
void solve(){
int n; cin >> n;
tree<int> T(n);
vector<pair<int, int>> sdeg(n);
vector<int> deg(n);
vector<vector<int>> tmp_es(n-1);
vector<pair<int, int>> es;
for(int v=0; v<n; v++){
int c; cin >> c;
sdeg[v] = {c, v};
deg[v] = c;
for(int i=0; i<c; i++){
int id; cin >> id;
id--;
tmp_es[id].push_back(v);
}
}
for(auto vec : tmp_es){
es.pb({min(vec[0], vec[1]), max(vec[0], vec[1])});
T[vec[0]].pb(vec[1]);
T[vec[1]].pb(vec[0]);
}
sort(all(es));
sort(all(sdeg), greater<pair<int, int>>());
auxiliary_tree<int> auxiliary_tree(T, 0);
tree<int> AT(n);
// dp[v][0]:=頂点vで頂点vの親との辺を使わない
// dp[v][1]:=頂点vで頂点vの親との辺を使う
vector<vector<int>> dp(n, vector<int>(2, 0));
vector<int> cnt(n, 0);
for(int q=1; q<n; q++){
vector<int> vs;
for(auto [d, v] : sdeg){
if(q <= d) vs.push_back(v);
else break;
}
if(vs.empty()){
cout << 0 << " ";
continue;
}
auxiliary_tree.build(vs.size(), vs, AT);
for(int v : vs) if(q <= deg[v]) cnt[v] = deg[v] - (int)AT[v].size();
function<void(int, int)> dfs = [&](int v, int p){
vector<int> diff;
int sum = 0;
for(auto e : AT[v]) if(e.to != p){
dfs(e.to, v);
diff.push_back(dp[e.to][0]-dp[e.to][1]);
sum += dp[e.to][1];
}
sort(all(diff), greater<int>());
if(v == vs[0]){
// calc dp[0]
if(q <= deg[v]){
dp[v][0] = 1 + sum;
if(cnt[v] < q){
int rest = q - cnt[v];
for(int i=0; i<min(rest, (int)diff.size()); i++) dp[v][0] += diff[i];
}
}
dp[v][0] = max(dp[v][0], sum);
}else{
if(binary_search(all(es), make_pair(min(p, v), max(p, v)))){
// 辺(p, v)が存在する場合
// calc dp[0]
if(q+1 <= deg[v]){
dp[v][0] = 1 + sum;
if(cnt[v] < q){
int rest = q - cnt[v];
for(int i=0; i<min(rest, (int)diff.size()); i++) dp[v][0] += diff[i];
}
}
dp[v][0] = max(dp[v][0], sum);
// calc dp[1]
if(q <= deg[v]){
dp[v][1] = 1 + sum;
if(cnt[v] < q-1){
int rest = q-1-cnt[v];
for(int i=0; i<min(rest, (int)diff.size()); i++) dp[v][1] += diff[i];
}
}
}else{
// 辺(p, v)が存在しない場合
if(q <= deg[v]){
dp[v][0] = 1 + sum;
if(cnt[v] < q-1){
int rest = q-1-cnt[v];
for(int i=0; i<min(rest, (int)diff.size()); i++) dp[v][0] += diff[i];
}
}
dp[v][0] = max(dp[v][0], sum);
}
dp[v][1] = max(dp[v][1], dp[v][0]);
}
}; dfs(vs[0], -1);
cout << dp[vs[0]][0] << " ";
// erase
for(int v : vs) AT[v].clear();
for(int v : vs) dp[v][0] = dp[v][1] = cnt[v] = 0;
}
cout << "\n";
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int T=1;
//cin >> T;
while(T--) solve();
}