oj.uz

답안 #446556

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446556 2021-07-22T12:15:26 Z ComPhyPark 낙하산 고리들 (IOI12_rings) C++14
0 / 100
 3499 ms 119460 KB 
#include<cstdio>
#include<vector>
using namespace std;
const int SZ = 1000010;
int min(int a, int b) { return a < b ? a : b; }
int n;
int cycleNum;
vector<int>l[SZ];
typedef struct Graph {
	int st[4], ts[3];
	int p[SZ], sz[SZ], ln[SZ];
	bool is3E[SZ], isCX[SZ];
	int x;
	void init() {
		x = n;
		st[0] = ts[0] = n;
		st[1] = st[2] = st[3] = ts[1] = ts[2] = 0;
		for (int i = 0; i < n; i++) {
			p[i] = i;
			sz[i] = 1;
			ln[i] = 0;
			is3E[i] = isCX[i] = false;
		}
	}
	void init(int X) {
		init();
		x = X;
		int i, a, b, c;
		for (i = 0; i < n; i++) {
			for (int e : l[i]) {
				if (e > i) {
					if (e == x || i == x) {
						isCX[e + i - x] = true;
						continue;
					}
					a = f(e), b = f(i);
					if (a != b) {
						p[b] = a;
						ln[a] += ln[b];
						sz[a] += sz[b];
					}
					ln[a]++;
				}
			}
			c = gC(i);
			st[min(c, 3)]++;
			if (c > 2)is3E[f(i)] = true;
		}
		for (i = 0; i < n; i++) {
			if (i == p[i])ts[gT(i)]++;
		}
	}
	int f(int a) {
		return a == p[a] ? a : p[a] = f(p[a]);
	}
	int gC(int A) {
		if (A == x)return 0;
		return l[A].size() - (isCX[A] ? 1 : 0);
	}
	void u(int A, int B) {
		int a = f(A), b = f(B);
		if (a != b) {
			p[b] = a;
			ts[gT(a)]--;
			ts[gT(b)]--;
			ln[a] += ln[b];
			sz[a] += sz[b];
			is3E[a] |= is3E[b];
		}
		else {
			ts[gT(a)]--;
		}
	}
	void Con(int A, int B) {
		int a = f(A), c = gC(A);
		if (x == n) {
			st[min(c, 3)]--;
			l[A].push_back(B);
			st[min(c + 1, 3)]++;
		}
		else {
			st[min(c - 1, 3)]--;
			st[min(c, 3)]++;
		}
		if (c >= 3)is3E[a] = true;
	}
	int gT(int a) {
		if (is3E[a]) {
			return 2;
		}
		else if (sz[a] == ln[a]) {
			return 1;
		}
		else {
			return 0;
		}
	}
	void Link(int A, int B) {
		if (A == x || B == x) {
			isCX[A + B - x] = true;
			return;
		}
		u(A, B);
		Con(A, B);
		Con(B, A);
		int a = f(A);
		ln[a]++;
		ts[gT(a)]++;
	}
	bool isChain() {
		return (ts[1] + ts[2] == 0);
	}
}Graph;
Graph MG, GV[4];
int GS;
void Init(int N) {
	cycleNum = n = N;
	MG.init();
}
void Link(int A, int B) {
	bool p = (MG.st[3] == 0);
	MG.Link(A, B);
	for (int i = 0; i < GS; i++) {
		GV[i].Link(A, B);
	}
	if (MG.gT(MG.f(A)) == 1)cycleNum = MG.f(A);
	if (MG.gT(MG.f(B)) == 1)cycleNum = MG.f(B);
	if (p && MG.st[3]) {
		int a = A;
		if (l[A].size() < 3)a = B;
		GS = l[a].size() + 1;
		GV[l[a].size()].init(a);
		for (int i = 0; i < l[a].size(); i++) {
			GV[i].init(l[a][i]);
		}
	}
}
int CountCritical() {
	if (MG.ts[2]) {
		int r = 0;
		for (int i = 0; i < GS; i++) {
			if (GV[i].isChain())r++;
		}
		return r;
	}
	else if (MG.ts[1]) {
		if (MG.ts[1] > 1)return 0;
		return MG.sz[cycleNum];
	}
	else {
		return n;
	}
}

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:133:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   for (int i = 0; i < l[a].size(); i++) {
      |                   ~~^~~~~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23756 KB Output is correct
2 Correct 18 ms 24404 KB Output is correct
3 Correct 20 ms 24488 KB Output is correct
4 Correct 16 ms 23784 KB Output is correct
5 Correct 17 ms 23964 KB Output is correct
6 Correct 17 ms 24012 KB Output is correct
7 Incorrect 16 ms 24292 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 506 ms 47248 KB Output is correct
2 Correct 2319 ms 103664 KB Output is correct
3 Correct 3499 ms 119460 KB Output is correct
4 Correct 1172 ms 68636 KB Output is correct
5 Correct 1180 ms 68748 KB Output is correct
6 Correct 1098 ms 67812 KB Output is correct
7 Correct 3314 ms 119080 KB Output is correct
8 Incorrect 2356 ms 117220 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23756 KB Output is correct
2 Correct 18 ms 24404 KB Output is correct
3 Correct 20 ms 24488 KB Output is correct
4 Correct 16 ms 23784 KB Output is correct
5 Correct 17 ms 23964 KB Output is correct
6 Correct 17 ms 24012 KB Output is correct
7 Incorrect 16 ms 24292 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23756 KB Output is correct
2 Correct 18 ms 24404 KB Output is correct
3 Correct 20 ms 24488 KB Output is correct
4 Correct 16 ms 23784 KB Output is correct
5 Correct 17 ms 23964 KB Output is correct
6 Correct 17 ms 24012 KB Output is correct
7 Incorrect 16 ms 24292 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23756 KB Output is correct
2 Correct 18 ms 24404 KB Output is correct
3 Correct 20 ms 24488 KB Output is correct
4 Correct 16 ms 23784 KB Output is correct
5 Correct 17 ms 23964 KB Output is correct
6 Correct 17 ms 24012 KB Output is correct
7 Incorrect 16 ms 24292 KB Output isn't correct
8 Halted 0 ms 0 KB -