Submission #1206107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206107		gs14004	Information (CEOI08_information)	C++20	42 / 100	85 ms	20552 KiB

information

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);

vector<vector<pi>> gph;
vector<int> tr, par, vis, pae;
int s2;

vector<int> ord;

void dfs1(int x) {
	vis[x] = 1;
	ord.push_back(x);
	for (auto &[i, y] : gph[x]) {
		if (!vis[y] && tr[i] == 0) {
			par[y] = x;
			pae[y] = i;
			tr[i] = 1;
			dfs1(y);
		}
	}
}

void dfs2(int x) {
	vis[x] = 1;
	for (auto &[i, y] : gph[x]) {
		if (!vis[y] && tr[i] == 0) {
			tr[i] = 2;
			dfs2(y);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	cr(gph, n);
	cr(tr, m);
	cr(par, n);
	cr(pae, n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		gph[u].push_back({i, v});
	}
	cr(vis, n);
	dfs1(0);
	if (count(all(vis), 1) < n) {
		cout << "NO\n";
		return 0;
	}
	cr(vis, n);
	dfs2(0);
	while (count(all(vis), 1) < n) {
		int v = -1;
		for (int j = sz(ord) - 1; j > 0; j--) {
			if (vis[par[ord[j]]] && !vis[ord[j]]) {
				v = ord[j];
				break;
			}
			tr[pae[ord[j]]] = 0;
		}
		tr[pae[v]] = 2;
		cr(vis, n);
		dfs1(0);
		if (count(all(vis), 1) < n) {
			cout << "NO\n";
			return 0;
		}
		cr(vis, n);
		dfs2(0);
	}
	vector<int> ans[2];
	for (int i = 0; i < m; i++) {
		if (tr[i])
			ans[tr[i] - 1].push_back(i + 1);
	}
	for (int i = 0; i < 2; i++) {
		for (auto &j : ans[i])
			cout << j << " ";
		cout << "\n";
	}
}

• Subtask 1: 0 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 0 / 4
• Subtask 11: 0 / 4
• Subtask 12: 0 / 4
• Subtask 13: 0 / 4
• Subtask 14: 4 / 4
• Subtask 15: 4 / 4
• Subtask 16: 0 / 4
• Subtask 17: 0 / 4
• Subtask 18: 0 / 4
• Subtask 19: 4 / 4
• Subtask 20: 0 / 4
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 0 / 5
• Subtask 24: 0 / 5