oj.uz

답안 #587221

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
587221 2022-07-01T13:55:22 Z GioChkhaidze 낙하산 고리들 (IOI12_rings) C++14
20 / 100
 1815 ms 138856 KB 
#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second

using namespace std;

const int Nn = 1e6 + 6;

bool cycle, new_cycle = false, REKT, f[Nn], us[Nn], in_cycle[Nn];
int n, ans, CM = -1, degreemax, len, comp, p[Nn], sz[Nn], pr[Nn];
set < pair < int , int > > st;
vector < int > v[Nn];

int P(int x) {
	if (p[x] == x) return x;
	return p[x] = P(p[x]);
}

void Init(int N_) {
	n = ans = N_;
	degreemax = 0;
	for (int i = 0; i < n; ++i) {
		st.insert({v[i].size(), i});
		p[i] = i;
	}
}

void dfs(int x, int p, int fn) {
	pr[x] = p;
	if (x == fn)  { 
		len = 1;
		cycle = true; 
		in_cycle[x] = true;
		while (x != pr[x]) {
			++len;
			x = pr[x];
			in_cycle[x] = true;
		}
		return ;
	}
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		if (to != p) dfs(to, x, fn);
		if (cycle) return ;
	}
}

bool okr;
void wfs(int x, int p, int fn) {
	pr[x] = p;
	if (CM == -1 && in_cycle[x]) CM = x;
		else
	if (CM != x && in_cycle[x]) REKT = true;
		else
	if (CM == x && in_cycle[x]) okr = true;
	
	if (x == fn)  { 
		new_cycle = true; 
		in_cycle[x] = true;
		while (x != pr[x]) {
			x = pr[x];
			in_cycle[x] = true;
		}
		return ;
	}
	
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		if (to != p) wfs(to, x, fn);
		if (new_cycle || REKT) return ;
	}
}

void Link(int A, int B) {
	int ap = P(A), bp = P(B);	
	if (ap != bp) {
		if (sz[ap] < sz[bp]) swap(ap, bp);	
		sz[ap] += sz[bp];
		p[bp] = ap;
	}
		else {
		if (!cycle) {
			//comp = A;
			dfs(A, A, B);
			assert(cycle == true);
		}		
			else
		if (cycle) {
			if (!REKT) {
				new_cycle = false;
				if (CM == -1) {
					wfs(A, A, B);
					if (CM == -1) {
						REKT = true;
					}
				}
					else {
					okr = false;
					wfs(A, A, B);
					if (!okr) REKT = true;
				}
			}
		}
	}
	
	st.erase(st.find({v[A].size(), A}));
	st.erase(st.find({v[B].size(), B}));
	v[A].pb(B), v[B].pb(A);
	st.insert({v[A].size(), A});
	st.insert({v[B].size(), B});
	if (v[A].size() > v[degreemax].size()) degreemax = A;
	if (v[B].size() > v[degreemax].size()) degreemax = B;
}

bool check(int x) {
	if (cycle && (CM == -1 && !in_cycle[x])) return 0;
	st.erase(st.find({v[x].size(), x}));
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		st.erase(st.find({v[to].size(), to}));
		st.insert({v[to].size() - 1, to});
	}
	
	bool ok = true;
	if (st.size() && (*st.rbegin()).f > 2) ok = false;
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		st.erase(st.find({v[to].size() - 1, to}));
		st.insert({v[to].size(), to});
	}
	st.insert({v[x].size(), x});
	return ok;
}

int CountCritical() {
	if (n > 5000) degreemax += 1/0;
	if (REKT) return 0;
	
	if (v[degreemax].size() <= 2) {
		if (!cycle) return n;
		return len;
	}
	int res = 0;
	for (int i = 0; i < n; ++i) {
		res += check(i);
	}
	return res;
	/*
	if (v[degreemax].size() > 3) {
		if (cycle && !in_cycle[degreemax]) return 0;
		
		st.erase(st.find({v[degreemax].size(), degreemax}));
		if ((*st.rbegin()).f > 3) return 0;
		st.insert({v[degreemax].size(), degreemax});
		
		for (int i = 0; i < v[degreemax].size(); ++i) {
			us[v[degreemax][i]] = true;
		}
		
		bool ok = true;
		for (int i = 0; i < n; ++i) {
			if (i != degreemax && !us[i] && v[i].size() > 2) {
				ok = false;
				break;
			} 
		}
		
		for (int i = 0; i < v[degreemax].size(); ++i) {
			us[v[degreemax][i]] = false;
		}
		
		return ok;
	}
	
	if (v[degreemax].size() == 3) {
		int res = 0;
		res += check(degreemax);
		res += check(v[degreemax][0]);
		res += check(v[degreemax][1]);
		res += check(v[degreemax][2]);
		return res;
	}*/
}

Compilation message

rings.cpp: In function 'void dfs(int, int, int)':
rings.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 = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
rings.cpp: In function 'void wfs(int, int, int)':
rings.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
rings.cpp: In function 'bool check(int)':
rings.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
rings.cpp:128:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:138:30: warning: division by zero [-Wdiv-by-zero]
  138 |  if (n > 5000) degreemax += 1/0;
      |                             ~^~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 21 ms 24224 KB Output is correct
3 Correct 28 ms 24288 KB Output is correct
4 Correct 13 ms 23856 KB Output is correct
5 Correct 17 ms 24148 KB Output is correct
6 Correct 18 ms 24404 KB Output is correct
7 Correct 16 ms 24020 KB Output is correct
8 Correct 17 ms 24148 KB Output is correct
9 Correct 23 ms 24224 KB Output is correct
10 Correct 26 ms 24236 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 21 ms 24224 KB Output is correct
3 Correct 28 ms 24288 KB Output is correct
4 Correct 13 ms 23856 KB Output is correct
5 Correct 17 ms 24148 KB Output is correct
6 Correct 18 ms 24404 KB Output is correct
7 Correct 16 ms 24020 KB Output is correct
8 Correct 17 ms 24148 KB Output is correct
9 Correct 23 ms 24224 KB Output is correct
10 Correct 26 ms 24236 KB Output is correct
11 Incorrect 78 ms 24240 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 21 ms 24224 KB Output is correct
3 Correct 28 ms 24288 KB Output is correct
4 Correct 13 ms 23856 KB Output is correct
5 Correct 17 ms 24148 KB Output is correct
6 Correct 18 ms 24404 KB Output is correct
7 Correct 16 ms 24020 KB Output is correct
8 Correct 17 ms 24148 KB Output is correct
9 Correct 23 ms 24224 KB Output is correct
10 Correct 26 ms 24236 KB Output is correct
11 Incorrect 78 ms 24240 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 21 ms 24224 KB Output is correct
3 Correct 28 ms 24288 KB Output is correct
4 Correct 13 ms 23856 KB Output is correct
5 Correct 17 ms 24148 KB Output is correct
6 Correct 18 ms 24404 KB Output is correct
7 Correct 16 ms 24020 KB Output is correct
8 Correct 17 ms 24148 KB Output is correct
9 Correct 23 ms 24224 KB Output is correct
10 Correct 26 ms 24236 KB Output is correct
11 Runtime error 1815 ms 138856 KB Execution killed with signal 4
12 Halted 0 ms 0 KB -