oj.uz

Submission #351396

# Submission time Handle Problem Language Result Execution time Memory
351396 2021-01-20T03:08:05 Z Kevin_Zhang_TW Parachute rings (IOI12_rings) C++17
0 / 100
 2012 ms 125768 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
 
const int MAX_N = 1000005;
 
int N, glob;
 
struct dsu {
	vector<int> g, sz;
	vector<short> deg;
 
	int n, badcnt, allbad, answer;
 
	dsu() {};
	dsu (int n, int size) : n(n), answer(size), badcnt(0), allbad(0) { 
		g.resize(n), sz.resize(n, 1), deg.resize(n);
		iota(AI(g), 0); 
	}
 
	int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
 
	void M(int a, int b) { 
 
		if (max(++deg[a], ++deg[b]) >= 3) allbad = true;
 
		if (allbad) return;
 
		a = F(a), b = F(b);
		if (sz[a] < sz[b]) swap(a, b);
 
		if (a != b) {
			return sz[a] += sz[b], g[b] = a, void();
		}
		if (++badcnt == 2) allbad = true;
		answer = sz[a];
	}
	bool noring() { return badcnt == 0 && allbad == false; }
 
	int getans() { 
		return allbad ? 0 : answer;
	}
};
 
dsu alld, forone;
 
vector<int> edge[MAX_N];
 
bool iscan[MAX_N];
 
vector<int> big, can;
 
vector<dsu> forcan;
vector<pair<int,int>> alledge;
 
int over = -1, lst;

void canpush(int id) { if (iscan[id]) return; iscan[id] = true, can.pb(id); }
 
void Init(int N_) {
	for (int i = 0;i < N;++i) edge[i].clear(), iscan[i] = false, edge[i].shrink_to_fit();
	big.clear(), can.clear(), forcan.clear(), alledge.clear(), over = -1, lst = 0, alld = forone = dsu();

	N = N_;
	glob = N;
	alld = dsu(N, N);

}
 
void makebig() {
	if (lst == 0)
		forone = dsu(N, N-1);
	while (lst < alledge.size()) {
		auto [a, b] = alledge[lst++];
		if (a != over && b != over)
			forone.M(a, b);
	}
	if (!forone.noring()) glob = -1;
}
void superbig(int id) {
	if (over == -1) {
		over = id;
		return;
	}
	else if (over != id) {
		glob = -1;
		return;
	}
}
void adjust(int a, int b) {

	if (glob == -1) return;
 
	if (big.empty()) {
 
		alld.M(a, b);
 
		glob = alld.getans();
 
		return;
	}
 
 	// deal with old ones
 	int oldsize = can.size();
 	for (int i = 0;i < oldsize;++i) {
 		int x = can[i];
 		if (a != x && b != x)
 			forcan[i].M(a, b);
 	}
 
	// put new element into candidate
	for (int x : big) {
		// assert(edge[x].size() <= 3);
		canpush(x);
		for (int u : edge[x]) canpush(u);
	}

	for (int x : big) for (int y : big) if (x != y) {
		assert(edge[x].size() == 3);
		if (count(AI(edge[y]), x) == 0)
			glob = -1;
	}
	if (glob == -1) return;

	assert(can.size() <= 16);
	// examine new candidates
 
 	for (int i = oldsize;i < can.size();++i) {
 		forcan.pb(N, N-1);
 		int x = can[i];
 		for (auto [a, b] : alledge) if (a != x && b != x) {
 			forcan[i].M(a, b);
 		}
 	}
 
	// assert(forcan.size() == can.size());
 
	glob = 0;
 
 	// examine all candidates
 	for (int i = 0;i < can.size();++i) 
 		glob += forcan[i].noring();
 
}
void Link(int A, int B) {
	if (glob == -1) return;
 
	edge[A].pb(B), edge[B].pb(A);
 
	if (edge[A].size() == 3) big.pb(A);
	if (edge[B].size() == 3) big.pb(B);
 
	alledge.pb(A, B);
 
 	if (edge[A].size() > 3) superbig(A);
 	if (edge[B].size() > 3) superbig(B);
 
	if (over != -1) return makebig(), void();
 
 	if (big.size() > 4) {
 		glob = -1;
 		return;
 	}
	
	adjust(A, B);
}
 
int CountCritical() {
	if (glob == -1) return 0;
	if (over != -1) return forone.noring();
	return max(glob, 0);
}

Compilation message

rings.cpp: In constructor 'dsu::dsu(int, int)':
rings.cpp:26:25: warning: 'dsu::answer' will be initialized after [-Wreorder]
   26 |  int n, badcnt, allbad, answer;
      |                         ^~~~~~
rings.cpp:26:9: warning:   'int dsu::badcnt' [-Wreorder]
   26 |  int n, badcnt, allbad, answer;
      |         ^~~~~~
rings.cpp:29:2: warning:   when initialized here [-Wreorder]
   29 |  dsu (int n, int size) : n(n), answer(size), badcnt(0), allbad(0) {
      |  ^~~
rings.cpp: In function 'void makebig()':
rings.cpp:86:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  while (lst < alledge.size()) {
      |         ~~~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'void adjust(int, int)':
rings.cpp:141:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |   for (int i = oldsize;i < can.size();++i) {
      |                        ~~^~~~~~~~~~~~
rings.cpp:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   for (int i = 0;i < can.size();++i)
      |                  ~~^~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23788 KB Output is correct
2 Correct 19 ms 24300 KB Output is correct
3 Correct 19 ms 24428 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 18 ms 24044 KB Output is correct
6 Correct 19 ms 24172 KB Output is correct
7 Correct 17 ms 24044 KB Output is correct
8 Correct 18 ms 24044 KB Output is correct
9 Correct 20 ms 24428 KB Output is correct
10 Incorrect 20 ms 24428 KB Output isn't correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 50452 KB Output is correct
2 Correct 1332 ms 103552 KB Output is correct
3 Correct 305 ms 75116 KB Output is correct
4 Correct 1244 ms 74504 KB Output is correct
5 Correct 1255 ms 74312 KB Output is correct
6 Correct 1191 ms 72912 KB Output is correct
7 Correct 301 ms 74604 KB Output is correct
8 Correct 2012 ms 125768 KB Output is correct
9 Incorrect 1867 ms 112504 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23788 KB Output is correct
2 Correct 19 ms 24300 KB Output is correct
3 Correct 19 ms 24428 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 18 ms 24044 KB Output is correct
6 Correct 19 ms 24172 KB Output is correct
7 Correct 17 ms 24044 KB Output is correct
8 Correct 18 ms 24044 KB Output is correct
9 Correct 20 ms 24428 KB Output is correct
10 Incorrect 20 ms 24428 KB Output isn't correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23788 KB Output is correct
2 Correct 19 ms 24300 KB Output is correct
3 Correct 19 ms 24428 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 18 ms 24044 KB Output is correct
6 Correct 19 ms 24172 KB Output is correct
7 Correct 17 ms 24044 KB Output is correct
8 Correct 18 ms 24044 KB Output is correct
9 Correct 20 ms 24428 KB Output is correct
10 Incorrect 20 ms 24428 KB Output isn't correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23788 KB Output is correct
2 Correct 19 ms 24300 KB Output is correct
3 Correct 19 ms 24428 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 18 ms 24044 KB Output is correct
6 Correct 19 ms 24172 KB Output is correct
7 Correct 17 ms 24044 KB Output is correct
8 Correct 18 ms 24044 KB Output is correct
9 Correct 20 ms 24428 KB Output is correct
10 Incorrect 20 ms 24428 KB Output isn't correct