oj.uz

답안 #443822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443822 2021-07-12T07:06:00 Z ComPhyPark 낙하산 고리들 (IOI12_rings) C++14
0 / 100
 1272 ms 262148 KB 
#include<cstdio>
#include<vector>
#include<set>
using namespace std;
const int SZ = 1000010;
int min(int a, int b) { return a < b ? a : b; }
int n;
const bool ifDebug = false;
int cycleNum;
typedef struct Graph {
	vector<vector<int>>l;
	int st[5], ts[3];
	int p[SZ], sz[SZ], cs[SZ][4];
	int x;
	void init() {
		x = n;
		l.resize(n);
		st[0] = ts[0] = n;
		st[1] = st[2] = st[3] = st[4] = ts[1] = ts[2] = 0;
		for (int i = 0; i < n; i++) {
			p[i] = i;
			cs[i][0] = sz[i] = 1;
			cs[i][1] = cs[i][2] = cs[i][3] = 0;
		}
	}
	void init(int X, Graph* G) {
		init();
		x = X;
		for (int i = 0; i < n; i++) {
			for (int e : (*G).l[i]) {
				if (e < i)Link(e, i);
			}
		}
	}
	int f(int a) {
		vector<int>v;
		while (a != p[a]) {
			v.push_back(a);
			a = p[a];
		}
		for (int e : v)p[e] = a;
		return a;
	}
	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)]--;
			for (int i = 0; i < 5; i++) {
				cs[a][i] += cs[b][i];
			}
			sz[a] += sz[b];
		}
		else {
			ts[gT(a)]--;
		}
	}
	void Con(int A, int B) {
		int a = f(A);
		cs[a][min(l[A].size(), 3)]--;
		st[min(l[A].size(), 4)]--;
		l[A].push_back(B);
		cs[a][min(l[A].size(), 3)]++;
		st[min(l[A].size(), 4)]++;
	}
	int gT(int a) {
		if (cs[a][3]) {
			return 2;
		}
		else if (cs[a][2] && (cs[a][1] + cs[a][0] == 0)) {
			return 1;
		}
		else {
			return 0;
		}
	}
	void Link(int A, int B) {
		if (A == x || B == x)return;
		u(A, B);
		Con(A, B);
		Con(B, A);
		int a = f(A);
		ts[gT(a)]++;
	}
	bool isChain() {
		return (ts[1] + ts[2] == 0);
	}
	void PR() {
		if (!ifDebug)return;
		printf("-------%d-------\n", x);
		for (int a = 0; a < n; a++) {
			if (a == p[a]) {
				printf("[%d(%d,%d)]", a, sz[a], gT(a));
				for (int b = 0; b < 4; b++)printf(" %d", cs[a][b]);
				printf("\n");
			}
			else {
				printf("%d->%d\n", a, f(a));
			}
		}
		printf("-----------------\n");
	}
}Graph;
Graph MG, GV[4];
int GS;
//type: 0-chain/1-cycle/2-3 exists/3-4 exists
void Init(int N) {
	cycleNum = n = N;
	MG.init();
}
void Link(int A, int B) {
	bool p = (MG.st[3] + MG.st[4] == 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]) {
		if (ifDebug)printf("걸렸구나!!!!!!!!!\n");
		int a = A;
		if (MG.l[A].size() < 3)a = B;
		GV[GS++].init(a, &MG);
		//return;
		for (int e : MG.l[a]) {
			GV[GS++].init(e, &MG);
		}
	}
}
int CountCritical() {
	if (MG.ts[2]) {
		if (ifDebug)printf(">=3 Exists");
		int r = 0;
		for (int i = 0; i < GS; i++) {
			if (GV[i].isChain())r++;
		}
		return r;
	}
	else if (MG.ts[1]) {
		if (ifDebug)printf("cycle Exists");
		if (MG.ts[1] > 1)return 0;
		return MG.sz[cycleNum];
	}
	else {
		if (ifDebug)printf("Already Chain");
		return n;
	}
}

Compilation message

rings.cpp: In member function 'void Graph::u(int, int)':
rings.cpp:51:14: warning: iteration 4 invokes undefined behavior [-Waggressive-loop-optimizations]
   51 |     cs[a][i] += cs[b][i];
      |     ~~~~~~~~~^~~~~~~~~~~
rings.cpp:50:22: note: within this loop
   50 |    for (int i = 0; i < 5; i++) {
      |                    ~~^~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 10 ms 1996 KB Output is correct
3 Correct 12 ms 2348 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

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

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 10 ms 1996 KB Output is correct
3 Correct 12 ms 2348 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 10 ms 1996 KB Output is correct
3 Correct 12 ms 2348 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 10 ms 1996 KB Output is correct
3 Correct 12 ms 2348 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -