oj.uz

답안 #285410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
285410 2020-08-28T22:30:22 Z c4ts0up 낙하산 고리들 (IOI12_rings) C++17
0 / 100
 183 ms 262148 KB 
// c4ts0up
// Rings - IOI 2012
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int NMAX = 1e5+5;

int n, t1, t2, t2b, t3, t3b, t4;
vector <int> Adj[NMAX], parent;
vector <char> colour;
unordered_set <int> ciclo;

void Init(int N_) {
	n = N_;
	colour.resize(n);
	parent.resize(n);
}

void Link(int A, int B) {
	Adj[A].pb(B);
	Adj[B].pb(A);
}

void DFS_Visit(int u) {
	//cerr << "Visitando " << u << " (" << colour[u] << ")" << endl;
	//colour[u] = 'G';
	
	bool be = false;
	int sz = Adj[u].size();
	
	for (int v : Adj[u]) {
		// de ahí venimos
		if (parent[u] == v) continue;

		// hay un ciclo, lo vamos a guardar
		if (colour[v] == 'G') {
			be = true;
			
			if (parent[v] == -1) parent[v] = u;
			
			// guardamos el ciclo, del cual tenemos que sacar el elemento para romper
			int curr = u;
			while (curr != v) {
				ciclo.insert(curr);
				curr = parent[curr];
			}
			ciclo.insert(v);
		}
		else if (colour[v] == 'B') {}
		else parent[v] = u, DFS_Visit(v);
	}
	
	if (sz <= 1) t1++;
	else if (sz == 2 && !be) t2++;
	else if (sz == 2 && be) t2b++;
	else if (sz == 3 && !be) t3++;
	else if (sz == 3 && be) t3b++;
	else t4++;
	
	colour[u] = 'B';
}

void DFS() {
	//cerr << "Entrando a DFS..." << endl;
	for (int i=0; i<n; i++) colour[i] = 'W', parent[i] = -1;
	
	t1 = 0;
	t2 = 0;
	t2b = 0;
	t3 = 0;
	t3b = 0;
	t4 = 0;
	
	// visitamos todos los nodos
	for (int i=0; i<n; i++) {
		if (colour[i] == 'W') DFS_Visit(i);
	}
}

int CountCritical() {
	//cerr << "Entrando a CC..." << endl;
	DFS();
	
	// si hay un t4, toca quitarlo
	if (t4) return 1;
	// si hay un t3 con ciclo, toca quitarlo o a uno de sus vecinos del ciclo
	else if (t3b) {
		//cerr << "Hay un t3b" << endl;
		int a, b = 0, c = 0;
		for (int x : ciclo) {
			if (Adj[x].size() == 3) {
				a = x;
				break;
			}
		}
		
		for (int x : Adj[a]) {
			if (ciclo.count(x) && !b) b = x;
			else if (ciclo.count(x) && b) c = x;
		}
		
		// Si alguno de los dos vecinos tiene tres aristas, solo podemos quitar ese o el otro
		if (Adj[b].size() == 3 || Adj[c].size() == 3) return 2;
		else return 3;
	}
	// si hay un t3 sin ciclos
	else if (t3) {
		//cerr << "Hay un t3" << endl;
		int a, b, c, d;
		for (int i=0; i<n; i++) {
			if (Adj[i].size() == 3){
				 a = i;
				 break;
			}
		}
		
		b = Adj[a][0];
		c = Adj[a][1];
		d = Adj[a][2];
		
		// 2 de los vecinos tienen tres, entonces solo podemos tomar el que tenemos
		if ((Adj[b].size() == 3 && Adj[c].size() == 3) || (Adj[b].size() == 3 && Adj[d].size() == 3) || (Adj[c].size() == 3 && Adj[d].size() == 3)) return 1;
		// 1 de los vecinos tiene tres
		else if (Adj[b].size() == 3 || Adj[c].size() == 3 || Adj[d].size() == 3) return 2;
		// ninguno de los vecinos tiene tres, entonces podemos quitar cualquiera de los cuatro elementos
		else return 4;
	}
	// si hay un t2 con ciclos
	else if (t2b) {
		//cerr << "Hay un t2b" << endl;
		return (int)ciclo.size();
	}
	else return n;
}

Compilation message

rings.cpp: In function 'int CountCritical()':
rings.cpp:90:7: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |   int a, b = 0, c = 0;
      |       ^
rings.cpp:110:7: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |   int a, b, c, d;
      |       ^

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 4 ms 2944 KB Output is correct
3 Correct 4 ms 2944 KB Output is correct
4 Runtime error 183 ms 262148 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 10624 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 4 ms 2944 KB Output is correct
3 Correct 4 ms 2944 KB Output is correct
4 Runtime error 183 ms 262148 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 4 ms 2944 KB Output is correct
3 Correct 4 ms 2944 KB Output is correct
4 Runtime error 183 ms 262148 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 4 ms 2944 KB Output is correct
3 Correct 4 ms 2944 KB Output is correct
4 Runtime error 183 ms 262148 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -