oj.uz

답안 #350278

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
350278 2021-01-19T04:45:16 Z Kevin_Zhang_TW 낙하산 고리들 (IOI12_rings) C++17
20 / 100
 4000 ms 60524 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, deg;

	int n, badcnt, allbad, answer;

	dsu() {};
	dsu (int n, int size) : n(n), answer(size), badcnt(0), allbad(0) { 
		deg = g = vector<int>(n);
		sz = vector<int>(n, 1);
		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;
		// merging into a ring
		// which means you have to remove objects on the ring
		// all of them is ok, since max deg is 2
		// I only care when max deg is <= 2
		// and a ring cannot merge with other for max deg <= 2
		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;

void canpush(int id) { if (iscan[id]) return; iscan[id] = true, can.pb(id); }

void Init(int N_) {
	N = N_;
	glob = N;
	alld = dsu(N, N);
	assert(N <= 20000);
// 	for (int i = 0;i < N;++i)
// 		adsu[i] = dsu(N, N-1);
}

vector<pair<int,int>> alledge;
// TODO big crisis
// new edge is {a, b}
int over = -1;

void pushbig(int id) {
	if (id == over) return;

}
void adjust(int a, int b) {
	if (glob == -1) return;


	DE(a, b);

	if (big.empty()) {
		alld.M(a, b);
		glob = alld.getans();
		return;
	}

// 	pushbig(a), pushbig(b);
// 
// 	if (over != -1) {
// 		if (a != over && b != over)
// 			forone.M(a, b);
// 		glob = forone.getans() == N - 1 ? 1 : -1;
// 	}


	// 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) {
		canpush(x);
		for (int u : edge[x]) canpush(u);
	}
	// 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);

 	if (big.size() > 4) {
 		glob = -1;
 		return;
 	}
	
	alledge.pb(A, B);


	return ;
	adjust(A, B);
}

int CountCritical() {
	if (glob == -1) return 0;
	int res = 0;
	for (int i = 0;i < N;++i) {
		dsu D(N, N - 1);
		for (auto [a, b] : alledge) if (a != i && b != i)
			D.M(a, b);
		if (D.noring()) ++res;
	}
	return res;
	return glob;
}

Compilation message

rings.cpp: In constructor 'dsu::dsu(int, int)':
rings.cpp:25:25: warning: 'dsu::answer' will be initialized after [-Wreorder]
   25 |  int n, badcnt, allbad, answer;
      |                         ^~~~~~
rings.cpp:25:9: warning:   'int dsu::badcnt' [-Wreorder]
   25 |  int n, badcnt, allbad, answer;
      |         ^~~~~~
rings.cpp:28:2: warning:   when initialized here [-Wreorder]
   28 |  dsu (int n, int size) : n(n), answer(size), badcnt(0), allbad(0) {
      |  ^~~
rings.cpp: In function 'void adjust(int, int)':
rings.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
rings.cpp:97:2: note: in expansion of macro 'DE'
   97 |  DE(a, b);
      |  ^~
rings.cpp:129:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |  for (int i = oldsize;i < can.size();++i) {
      |                       ~~^~~~~~~~~~~~
rings.cpp:142:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |  for (int i = 0;i < can.size();++i)
      |                 ~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 200 ms 24168 KB Output is correct
3 Correct 214 ms 24300 KB Output is correct
4 Correct 33 ms 23916 KB Output is correct
5 Correct 180 ms 24172 KB Output is correct
6 Correct 568 ms 24240 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 378 ms 24044 KB Output is correct
9 Correct 278 ms 24232 KB Output is correct
10 Correct 328 ms 24300 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 60 ms 60524 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 200 ms 24168 KB Output is correct
3 Correct 214 ms 24300 KB Output is correct
4 Correct 33 ms 23916 KB Output is correct
5 Correct 180 ms 24172 KB Output is correct
6 Correct 568 ms 24240 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 378 ms 24044 KB Output is correct
9 Correct 278 ms 24232 KB Output is correct
10 Correct 328 ms 24300 KB Output is correct
11 Execution timed out 4090 ms 24096 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 200 ms 24168 KB Output is correct
3 Correct 214 ms 24300 KB Output is correct
4 Correct 33 ms 23916 KB Output is correct
5 Correct 180 ms 24172 KB Output is correct
6 Correct 568 ms 24240 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 378 ms 24044 KB Output is correct
9 Correct 278 ms 24232 KB Output is correct
10 Correct 328 ms 24300 KB Output is correct
11 Execution timed out 4090 ms 24096 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 200 ms 24168 KB Output is correct
3 Correct 214 ms 24300 KB Output is correct
4 Correct 33 ms 23916 KB Output is correct
5 Correct 180 ms 24172 KB Output is correct
6 Correct 568 ms 24240 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 378 ms 24044 KB Output is correct
9 Correct 278 ms 24232 KB Output is correct
10 Correct 328 ms 24300 KB Output is correct
11 Runtime error 60 ms 60524 KB Execution killed with signal 6 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -