oj.uz

답안 #760708

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
760708 2023-06-18T08:09:46 Z NothingXD 낙하산 고리들 (IOI12_rings) C++17
52 / 100
 76 ms 55968 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cout << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;

int n, par[10][maxn], cycle;
bool bad[10];
vector<int> g[maxn][10], ver;

int getpar(int idx, int v){
	return (par[idx][v] < 0? v: par[idx][v] = getpar(idx, par[idx][v]));
}

bool merge(int idx, int x, int y){
	int u = getpar(idx, x);
	int v = getpar(idx, y);
	if (u == v) return false;
	par[idx][u] += par[idx][v];
	par[idx][v] = u;
	return true;
}

void Init(int N_) {
	memset(par, -1, sizeof par);
	n = N_;
}

void Link(int A, int B) {
	if (!bad[0]){
		g[A][0].push_back(B);
		g[B][0].push_back(A);
		if (g[A][0].size() == 3){
			bad[0] = true;
			ver.push_back(A);
			for (auto x: g[A][0])ver.push_back(x);
			for (int i = 1; i <= ver.size(); i++){
				for (int j = 0; j < n; j++){
					if (j == ver[i-1]) continue;
					for (auto u: g[j][0]){
						if (u < j || u == ver[i-1]) continue;
						g[j][i].push_back(u);
						g[u][i].push_back(j);
						if (max(g[j][i].size(), g[u][i].size()) > 2 || !merge(i, j, u)) bad[i] = true;
					}
				}
			}
		}
		else if (g[B][0].size() == 3){
			bad[0] = true;
			ver.push_back(B);
			for (auto x: g[B][0])ver.push_back(x);
			for (int i = 1; i <= ver.size(); i++){
				for (int j = 0; j < n; j++){
					if (j == ver[i-1]) continue;
					for (auto u: g[j][0]){
						if (u < j || u == ver[i-1]) continue;
						g[j][i].push_back(u);
						g[u][i].push_back(j);
						if (max(g[j][i].size(), g[u][i].size()) > 2 || !merge(i, j, u)) bad[i] = true;
					}
				}
			}
		}
		if (!merge(0, A, B)){
			if (cycle != 0) bad[0] = true;
			cycle = -par[0][getpar(0, A)];
		}
		return;
	}
	for (int i = 1; i <= ver.size(); i++){
		if (A != ver[i-1] && B != ver[i-1]){
			g[A][i].push_back(B);
			g[B][i].push_back(A);
			if (max(g[A][i].size(), g[B][i].size()) > 2 || !merge(i, A, B)) bad[i] = true;
		}
	}
}

int CountCritical() {
	if (!bad[0]){
		if (cycle == 0) return n;
		return cycle;
	}
	int ans = 0;
	for (int i = 1; i <= ver.size(); i++){
		ans += (!bad[i]);
	}
	return ans;
}

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    for (int i = 1; i <= ver.size(); i++){
      |                    ~~^~~~~~~~~~~~~
rings.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    for (int i = 1; i <= ver.size(); i++){
      |                    ~~^~~~~~~~~~~~~
rings.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for (int i = 1; i <= ver.size(); i++){
      |                  ~~^~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for (int i = 1; i <= ver.size(); i++){
      |                  ~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 27604 KB Output is correct
2 Correct 18 ms 28256 KB Output is correct
3 Correct 17 ms 28372 KB Output is correct
4 Correct 14 ms 27664 KB Output is correct
5 Correct 16 ms 27732 KB Output is correct
6 Correct 17 ms 27868 KB Output is correct
7 Correct 17 ms 27812 KB Output is correct
8 Correct 17 ms 27824 KB Output is correct
9 Correct 17 ms 28424 KB Output is correct
10 Correct 18 ms 28476 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 27604 KB Output is correct
2 Correct 18 ms 28256 KB Output is correct
3 Correct 17 ms 28372 KB Output is correct
4 Correct 14 ms 27664 KB Output is correct
5 Correct 16 ms 27732 KB Output is correct
6 Correct 17 ms 27868 KB Output is correct
7 Correct 17 ms 27812 KB Output is correct
8 Correct 17 ms 27824 KB Output is correct
9 Correct 17 ms 28424 KB Output is correct
10 Correct 18 ms 28476 KB Output is correct
11 Correct 18 ms 28448 KB Output is correct
12 Correct 21 ms 29228 KB Output is correct
13 Correct 21 ms 29080 KB Output is correct
14 Correct 17 ms 28416 KB Output is correct
15 Correct 17 ms 28152 KB Output is correct
16 Correct 17 ms 27988 KB Output is correct
17 Correct 20 ms 28972 KB Output is correct
18 Correct 21 ms 29380 KB Output is correct
19 Correct 17 ms 27996 KB Output is correct
20 Correct 21 ms 29180 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 27604 KB Output is correct
2 Correct 18 ms 28256 KB Output is correct
3 Correct 17 ms 28372 KB Output is correct
4 Correct 14 ms 27664 KB Output is correct
5 Correct 16 ms 27732 KB Output is correct
6 Correct 17 ms 27868 KB Output is correct
7 Correct 17 ms 27812 KB Output is correct
8 Correct 17 ms 27824 KB Output is correct
9 Correct 17 ms 28424 KB Output is correct
10 Correct 18 ms 28476 KB Output is correct
11 Correct 18 ms 28448 KB Output is correct
12 Correct 21 ms 29228 KB Output is correct
13 Correct 21 ms 29080 KB Output is correct
14 Correct 17 ms 28416 KB Output is correct
15 Correct 17 ms 28152 KB Output is correct
16 Correct 17 ms 27988 KB Output is correct
17 Correct 20 ms 28972 KB Output is correct
18 Correct 21 ms 29380 KB Output is correct
19 Correct 17 ms 27996 KB Output is correct
20 Correct 21 ms 29180 KB Output is correct
21 Correct 30 ms 28756 KB Output is correct
22 Correct 46 ms 29328 KB Output is correct
23 Correct 42 ms 29692 KB Output is correct
24 Correct 71 ms 33480 KB Output is correct
25 Correct 26 ms 28372 KB Output is correct
26 Correct 68 ms 35920 KB Output is correct
27 Correct 45 ms 30088 KB Output is correct
28 Correct 76 ms 38800 KB Output is correct
29 Correct 50 ms 33632 KB Output is correct
30 Correct 59 ms 30796 KB Output is correct

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 27604 KB Output is correct
2 Correct 18 ms 28256 KB Output is correct
3 Correct 17 ms 28372 KB Output is correct
4 Correct 14 ms 27664 KB Output is correct
5 Correct 16 ms 27732 KB Output is correct
6 Correct 17 ms 27868 KB Output is correct
7 Correct 17 ms 27812 KB Output is correct
8 Correct 17 ms 27824 KB Output is correct
9 Correct 17 ms 28424 KB Output is correct
10 Correct 18 ms 28476 KB Output is correct
11 Runtime error 38 ms 55968 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -