oj.uz

Submission #365990

# Submission time Handle Problem Language Result Execution time Memory
365990 2021-02-12T16:25:27 Z kostia244 Potemkin cycle (CEOI15_indcyc) C++17
100 / 100
 779 ms 5876 KB 
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int maxn = 1002, maxm = 2e5 + 3;
int can[maxm][maxn], hv[maxn][maxn], vis[maxm], n, m;
vector<array<int, 2>> edges;
vector<int> cur;
void reduce() {
	int r = 0, l = 0;
	[&]() {
	while(r < cur.size()) {
		for(int i = r-2; i >= 0; i--) {
			if(hv[cur[r]][cur[i]]) {
				l = i;
				r++;
				return;
			}
		}
		r++;
	}
	}();
	for(int i = l; i < r; i++) cout << cur[i] << " "; cout << endl;
	exit(0);
}
void dfs(int ed) {
	vis[ed] = 2;
	auto [st, en] = edges[ed];
	cur.push_back(en);
	for(int i = 1; i <= n; i++) if(i != st && i != en) {
		if(hv[i][en] && hv[i][st]) continue;
		if(!hv[en][i]) continue;
		if(!vis[hv[en][i]-1]) {
			dfs(hv[en][i]-1);
		} else if(vis[hv[en][i]-1] == 2) {
			reverse(all(cur));
			while(cur.back() != en) cur.pop_back();
			cur.pop_back();
			reduce();
		}
	}
	vis[ed] = 1;
	cur.pop_back();
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	edges.resize(m);
	for(auto &[f, t] : edges) {
		cin >> f >> t;
	}
	for(int i = 0; i < m; i++) edges.push_back({edges[i][1], edges[i][0]});
	for(int i = 0; i < 2*m; i++) hv[edges[i][0]][edges[i][1]] = i+1;
	for(int i = 0; i < 2*m; i++) if(!vis[i]) {
		cur = {edges[i][0]};
		dfs(i);
	}
	cout << "no\n";
}

Compilation message

indcyc.cpp: In lambda function:
indcyc.cpp:12:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  while(r < cur.size()) {
      |        ~~^~~~~~~~~~~~
indcyc.cpp: In function 'void reduce()':
indcyc.cpp:23:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   23 |  for(int i = l; i < r; i++) cout << cur[i] << " "; cout << endl;
      |  ^~~
indcyc.cpp:23:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   23 |  for(int i = l; i < r; i++) cout << cur[i] << " "; cout << endl;
      |                                                    ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 2 ms 748 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1644 KB Output is correct
2 Correct 4 ms 1644 KB Output is correct
3 Correct 2 ms 1644 KB Output is correct
4 Correct 17 ms 1644 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1772 KB Output is correct
2 Correct 9 ms 1644 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 5496 KB Output is correct
2 Correct 45 ms 4688 KB Output is correct
3 Correct 481 ms 5388 KB Output is correct
4 Correct 200 ms 4816 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4688 KB Output is correct
2 Correct 224 ms 4848 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3704 KB Output is correct
2 Correct 315 ms 4344 KB Output is correct
3 Correct 16 ms 5492 KB Output is correct
4 Correct 779 ms 5876 KB Output is correct