Submission #1206117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206117		gs14004	Information (CEOI08_information)	C++20	100 / 100	259 ms	20568 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;
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);
	ord.clear();
	dfs1(0);
	if (sz(ord) < n) {
		cout << "NONE\n";
		return 0;
	}
	cr(vis, n);
	dfs2(0);
	while (count(all(vis), 1) < n) {
		int v = -1;
		for (int j = 1; j < sz(ord); j++) {
			if (vis[par[ord[j]]] && !vis[ord[j]]) {
				v = ord[j];
			}
			tr[pae[ord[j]]] = 0;
		}
		tr[pae[v]] = 2;
		cr(vis, n);
		ord.clear();
		dfs1(0);
		if (sz(ord) < n) {
			cout << "NONE\n";
			return 0;
		}
		for (int j = 0; j < m; j++)
			if (tr[j] == 2)
				tr[j] = 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: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 4 / 4
• Subtask 12: 4 / 4
• Subtask 13: 4 / 4
• Subtask 14: 4 / 4
• Subtask 15: 4 / 4
• Subtask 16: 4 / 4
• Subtask 17: 4 / 4
• Subtask 18: 4 / 4
• Subtask 19: 4 / 4
• Subtask 20: 4 / 4
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5
• Subtask 24: 5 / 5