제출 #1264387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264387		tminh	Railway (BOI17_railway)	C++20	0 / 100	76 ms	70588 KiB

railway

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

#define task ""
#define ll long long
#define endl '\n'
#define fi first
#define se second
#define vall(a) (a).begin(), (a).end()
#define sze(a) (int)a.size()
#define pii pair<int, int>
#define pll pair<ll, ll>


#define ep emplace_back
#define pb push_back
#define pf push_front


const ll mod = 1e9 + 7;
const int N = 1e6 + 5;
const ll oo = 1e18;

bool START;
int n, m, k, t = 0, dp[N], in[N], lg[N], h[N];
vector<pii> adj[N];

pii st[N][20];

void dfsb(int u, int p) {
	in[u] = ++t;
	st[t][0] = make_pair(h[u], u);
	for (auto [v, id] : adj[u]) {
		if (v == p) continue;
		h[v] = h[u] + 1;
		dfsb(v, u);
		st[++t][0] = make_pair(h[u], u);
	}
}

void build() {
	dfsb(1, 0);
	for (int i = 2; i <= t; ++i) lg[i] = lg[i >> 1] + 1;
	for (int i = 1; (1 << i) <= t; ++i) {
		for (int j = 1; j + (1 << i) - 1 <= t; ++j) {
			st[j][i] = min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
		}
	}
}
int lca(int u, int v) {
	if (in[u] < in[v]) swap(u, v);
	int k = lg[in[u] - in[v] + 1];
	return min(st[in[u] - (1 << k) + 1][k], st[in[v]][k]).se;
}

vector<int> ans;
void dfs(int u, int p) {
	for (auto[v, id] : adj[u]) {
		if (v == p) continue;
		dfs(v, u);
		if (dp[v] >= k) ans.pb(id);
		dp[u] += dp[v];
	}
}

bool cmp(int a, int b) {
	return in[a] < in[b];
}

int a[N];
inline void solve() {
	build();
	while(m--) {
		int t; cin >> t;
		for (int i = 1; i <= t; ++i) cin >> a[i];
		sort(a + 1, a + 1 + t, cmp);
		
		int lck = lca(a[t], a[1]);
		++dp[a[1]];
		++dp[a[t]];
		dp[lck] -= 2;

		for (int i = 2; i <= t; ++i) {
			lck = lca(a[i], a[i - 1]);
			++dp[a[i]];
			++dp[a[i - 1]];
			dp[lck] -= 2;
		}
	}
	dfs(1, 0);
	cout << sze(ans) << endl;
	for (int i : ans) cout << i << " ";
}


inline void input() {
    cin >> n >> m >> k;
    k <<= 1ll;
    for (int i = 1; i < n; ++i) {
    	int u, v;
    	cin >> u >> v;
    	adj[u].pb(make_pair(v, i));
    	adj[v].pb(make_pair(u, i));
    }
    return solve();
}
bool END;

int main() {
    if(fopen(task ".inp", "r")) {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    input();
    
    
    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << 's' << endl;
    cerr << "Memory: " << fabs ((&END - &START)) / 1048576.0 << "MB\n";
    return 0;
}

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

railway.cpp: In function 'int main()':
railway.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25