oj.uz

답안 #462517

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
462517 2021-08-10T17:01:06 Z kingfran1907 Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 55 ms 6212 KB 
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 1010;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, m;
vector< int > graph[maxn];
int eg[maxn][maxn];
bool bio[maxn];
bool er[maxn];
int dis[maxn];
queue< int > q;

void dfs(int x, vector< int > &v) {
	bio[x] = true;
	v.push_back(x);
	for (int tren : graph[x]) {
		if (!er[tren] && !bio[tren]) {
			dfs(tren, v);
		}
	}
}

void solve(vector< int > v) {
	if (v.size() == 0) return;
	int x = v[0];
	
	//printf("solve: ");
	//for (int tren : v) printf("%d ", tren);
	//printf("\n");
	
	vector< int > s, p;
	for (int i = 1; i < v.size(); i++) {
		bio[v[i]] = false;
		if (eg[x][v[i]]) s.push_back(v[i]);
		else p.push_back(v[i]);
	}
	
	for (int i = 1; i <= n; i++) er[i] = true;
	for (int tren : p) er[tren] = false;
	
	vector< vector<int> > vs, acs;
	for (int i = 0; i < p.size(); i++) {
		if (bio[p[i]]) continue;
		vector< int > tr;
		dfs(p[i], tr);
		vs.push_back(tr);
		
		//printf("comp: ");
		//for (int y : tr) printf("%d ", y);
		//printf("\n");
	}
	
	for (auto ax : vs) {
		vector< int > ps;
		int a = -1, b = -1;
		for (int tren : s) {
			for (int ing : ax) {
				if (eg[tren][ing]) {
					for (int p : ps) {
						if (eg[tren][p] == 0) {
							a = p, b = tren;
							break;
						}
					}
					if (a == -1) ps.push_back(tren);
					break;
				}
			}
			if (a != -1) break;
		}
		if (a == -1) continue;
		//printf("found: %d %d\n", a, b);
		
		for (int i = 1; i <= n; i++) dis[i] = -1;
		for (int tren : ax) dis[tren] = inf;
		dis[b] = inf, dis[a] = 0;
		
		q.push(a);
		while (!q.empty()) {
			int node = q.front();
			q.pop();
			
			for (int tren : graph[node]) {
				if (dis[tren] == inf) {
					dis[tren] = 1 + dis[node];
					q.push(tren);
				}
			}
		}
		
		vector< int > sol;
		int ptr = b;
		while (ptr != a) {
			sol.push_back(ptr);
			
			for (int tren : graph[ptr]) {
				if (dis[tren] + 1 == dis[ptr]) {
					ptr = tren;
					break;
				}
			}
		}
		reverse(sol.begin(), sol.end());
		
		printf("%d %d ", x, a);
		for (int tren : sol) printf("%d ", tren);
		printf("\n");
		exit(0);
	}
	solve(s);
	
	for (int i = 0; i < vs.size(); i++) {
		vector< int > tren = vs[i];
		for (int ac : s) {
			for (int ps : vs[i]) {
				if (eg[ps][ac]) {
					tren.push_back(ac);
					break;
				}
			}
		}
		solve(tren);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		
		graph[a].push_back(b);
		graph[b].push_back(a);
		eg[a][b] = eg[b][a] = 1;
	}
	
	memset(er, false, sizeof er);
	vector< int > v;
	for (int i = 1; i <= n; i++) 
		v.push_back(i);
	solve(v);
	printf("no\n");
	return 0;
}

Compilation message

indcyc.cpp: In function 'void solve(std::vector<int>)':
indcyc.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i = 1; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
indcyc.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for (int i = 0; i < p.size(); i++) {
      |                  ~~^~~~~~~~~~
indcyc.cpp:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |  for (int i = 0; i < vs.size(); i++) {
      |                  ~~^~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:138:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
indcyc.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 716 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1612 KB Output is correct
2 Correct 2 ms 1612 KB Output is correct
3 Correct 4 ms 1740 KB Output is correct
4 Correct 4 ms 1612 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 3 ms 1612 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 4808 KB Output is correct
2 Correct 13 ms 4940 KB Output is correct
3 Correct 32 ms 5348 KB Output is correct
4 Correct 16 ms 4872 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 4620 KB Output is correct
2 Correct 20 ms 4804 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 3164 KB Output is correct
2 Correct 25 ms 4620 KB Output is correct
3 Correct 34 ms 5752 KB Output is correct
4 Correct 55 ms 6212 KB Output is correct