oj.uz

Submission #365989

# Submission time Handle Problem Language Result Execution time Memory
365989 2021-02-12T16:18:56 Z kostia244 Potemkin cycle (CEOI15_indcyc) C++17
90 / 100
 844 ms 6516 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;
	while(r < cur.size()) {
		int ok = 1;
		for(int i = 1; i+1 < r; i++) {
			ok &= !hv[cur[r]][cur[i]];
		}
		if(!ok) break;
		if(r > 1 && hv[cur[r]][cur[0]]) {r++;break;}
		r++;
	}
	for(int i = 0; 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 function 'void reduce()':
indcyc.cpp:11:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  while(r < cur.size()) {
      |        ~~^~~~~~~~~~~~
indcyc.cpp:20:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   20 |  for(int i = 0; i < r; i++) cout << cur[i] << " "; cout << endl;
      |  ^~~
indcyc.cpp:20:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   20 |  for(int i = 0; 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 1 ms 364 KB Output is correct
5 Correct 1 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 384 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 748 KB Wrong adjacency

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 9 ms 1644 KB Output is correct
2 Correct 5 ms 1644 KB Output is correct
3 Correct 2 ms 1772 KB Output is correct
4 Correct 19 ms 1796 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1644 KB Output is correct
2 Correct 10 ms 1664 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 5752 KB Output is correct
2 Correct 46 ms 4816 KB Output is correct
3 Correct 534 ms 5880 KB Output is correct
4 Correct 197 ms 4816 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 4816 KB Output is correct
2 Correct 223 ms 4944 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 4472 KB Output is correct
2 Correct 326 ms 5112 KB Output is correct
3 Correct 17 ms 6004 KB Output is correct
4 Correct 844 ms 6516 KB Output is correct