oj.uz

Submission #760707

# Submission time Handle Problem Language Result Execution time Memory
760707 2023-06-18T08:06:20 Z NothingXD Parachute rings (IOI12_rings) C++17
52 / 100
 84 ms 56012 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;
					}
				}
			}
		}
		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

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27604 KB Output is correct
2 Correct 16 ms 28348 KB Output is correct
3 Correct 20 ms 28320 KB Output is correct
4 Correct 14 ms 27740 KB Output is correct
5 Correct 17 ms 27692 KB Output is correct
6 Correct 18 ms 27908 KB Output is correct
7 Correct 15 ms 27732 KB Output is correct
8 Correct 15 ms 27732 KB Output is correct
9 Correct 17 ms 28356 KB Output is correct
10 Correct 17 ms 28472 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 56012 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27604 KB Output is correct
2 Correct 16 ms 28348 KB Output is correct
3 Correct 20 ms 28320 KB Output is correct
4 Correct 14 ms 27740 KB Output is correct
5 Correct 17 ms 27692 KB Output is correct
6 Correct 18 ms 27908 KB Output is correct
7 Correct 15 ms 27732 KB Output is correct
8 Correct 15 ms 27732 KB Output is correct
9 Correct 17 ms 28356 KB Output is correct
10 Correct 17 ms 28472 KB Output is correct
11 Correct 20 ms 28360 KB Output is correct
12 Correct 22 ms 29152 KB Output is correct
13 Correct 20 ms 29012 KB Output is correct
14 Correct 17 ms 28372 KB Output is correct
15 Correct 17 ms 28252 KB Output is correct
16 Correct 21 ms 28120 KB Output is correct
17 Correct 21 ms 28888 KB Output is correct
18 Correct 21 ms 29268 KB Output is correct
19 Correct 19 ms 27988 KB Output is correct
20 Correct 21 ms 29180 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27604 KB Output is correct
2 Correct 16 ms 28348 KB Output is correct
3 Correct 20 ms 28320 KB Output is correct
4 Correct 14 ms 27740 KB Output is correct
5 Correct 17 ms 27692 KB Output is correct
6 Correct 18 ms 27908 KB Output is correct
7 Correct 15 ms 27732 KB Output is correct
8 Correct 15 ms 27732 KB Output is correct
9 Correct 17 ms 28356 KB Output is correct
10 Correct 17 ms 28472 KB Output is correct
11 Correct 20 ms 28360 KB Output is correct
12 Correct 22 ms 29152 KB Output is correct
13 Correct 20 ms 29012 KB Output is correct
14 Correct 17 ms 28372 KB Output is correct
15 Correct 17 ms 28252 KB Output is correct
16 Correct 21 ms 28120 KB Output is correct
17 Correct 21 ms 28888 KB Output is correct
18 Correct 21 ms 29268 KB Output is correct
19 Correct 19 ms 27988 KB Output is correct
20 Correct 21 ms 29180 KB Output is correct
21 Correct 28 ms 28668 KB Output is correct
22 Correct 36 ms 29264 KB Output is correct
23 Correct 43 ms 29748 KB Output is correct
24 Correct 59 ms 33484 KB Output is correct
25 Correct 31 ms 28420 KB Output is correct
26 Correct 65 ms 35908 KB Output is correct
27 Correct 47 ms 29988 KB Output is correct
28 Correct 84 ms 38784 KB Output is correct
29 Correct 53 ms 33648 KB Output is correct
30 Correct 57 ms 30832 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27604 KB Output is correct
2 Correct 16 ms 28348 KB Output is correct
3 Correct 20 ms 28320 KB Output is correct
4 Correct 14 ms 27740 KB Output is correct
5 Correct 17 ms 27692 KB Output is correct
6 Correct 18 ms 27908 KB Output is correct
7 Correct 15 ms 27732 KB Output is correct
8 Correct 15 ms 27732 KB Output is correct
9 Correct 17 ms 28356 KB Output is correct
10 Correct 17 ms 28472 KB Output is correct
11 Runtime error 36 ms 56012 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -