oj.uz

답안 #546158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
546158 2022-04-06T14:53:32 Z keta_tsimakuridze 낙하산 고리들 (IOI12_rings) C++14
52 / 100
 1230 ms 59468 KB 
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int,int>
const int N = 100000 + 5;
int n, sz = 0, h[N];
int cycle[7], rem[7], stop = 0, p[N][7];
set<pii> tried[6], deg;
vector<int> V[7][N];
void Init(int N_) {
  n = N_;
  for(int i = 0; i < n; i++) {
  	for(int t = 0; t < 6; t++) {
  		p[i][t] = i;
	}
	deg.insert({0, i});
  }
}
int find(int a, int t) {
	return (p[a][t] == a ? p[a][t] :  p[a][t] = find(p[a][t], t));	
}
void merge(int a,int b, int t) {
	a = find(a, t); b = find(b, t);
	if(a == b) return;
	p[a][t] = b;
	return;
}
void dfs(int a, int p) {
	h[a] = h[p] + 1;
	for(int i = 0; i < V[5][a].size(); i++) {
		if(V[5][a][i] == p) continue;
		if(sz) return;
		if(h[V[5][a][i]]) { 
			sz = h[a] - h[V[5][a][i]] + 1;
			return;
		} else dfs(V[5][a][i], a);
	}
}
void add(int a, int b, int t) {
	if(a == rem[t] || b == rem[t]) return;
	tried[t].erase({V[t][a].size(), a});
	tried[t].erase({V[t][b].size(), b});
	V[t][a].push_back(b); V[t][b].push_back(a);
	tried[t].insert({V[t][a].size(), a});
	tried[t].insert({V[t][b].size(), b});
	if(find(a, t) == find(b, t)) cycle[t] = 1;
	else merge(a, b, t);
	return;	
}
void Link(int a, int b) {
	deg.erase({V[5][a].size(), a});
	deg.erase({V[5][b].size(), b});
	V[5][a].push_back(b); V[5][b].push_back(a);
	deg.insert({V[5][a].size(), a});
	deg.insert({V[5][b].size(), b});
	if(find(a, 5) != find(b, 5)) {
		merge(a, b, 5);
	}
	else {
		if(!cycle[5]) {
			merge(a, b, 5);
			dfs(a, -1);
			cycle[5] = a + 1;
		}
		else if(find(a, 5) != find(cycle[5] - 1, 5)) {
			stop = 1;
		}
	}
	if(tried[0].size()) {
		add(a, b, 0);
	}
	if(tried[1].size()) {

		for(int i = 1; i <= 4; i++) add(a, b, i);
	}
	
}
void build(int t) {
	int u = rem[t];
	for(int i = 0; i < n; i++) {
		if(u == i) continue;
		for(int j = 0; j < V[5][i].size(); j++) {
			int v = V[5][i][j];
			if(v == u || v < i) continue;
			if(find(v, t) == find(i, t)) cycle[t] = 1;
			merge(i, v, t);
			V[t][i].push_back(v); V[t][v].push_back(i);
		}
	}
	for(int i = 0; i < n; i++) tried[t].insert({V[t][i].size(), i});	
}
int CountCritical() {
	if(stop) return 0; 
	if(!cycle[5] && (*--deg.end()).f <= 2) return n;
	if((*--deg.end()).f <= 2) return sz;
	
	if((*--deg.end()).f >= 4) {
		if(!tried[0].size()) {
			rem[0] = (*--deg.end()).s;
			build(0);
		}
		if((*--tried[0].end()).f <= 2 && !cycle[0]) return 1;
		stop = 1;
		return 0;
	}
	if(!tried[1].size()) {
		rem[1] = (*--deg.end()).s; 
		for(int i = 0; i < V[5][rem[1]].size(); i++) {
			rem[i + 2] = V[5][rem[1]][i]; 
		}
		for(int i = 1; i <= 4; i++) {
			build(i);
		}
	}
	int cn = 0;
	for(int i = 1; i <= 4; i++) {
		if((*--tried[i].end()).f <= 2 && !cycle[i]) cn++;
	}
	return cn;
}
/*
int main() {
	int n; cin >> n;
	Init(n);
	while(true) {
		int t, x;
		cin >> t;
		if(t == 0) {
			cout << CountCritical() << "_______________" << endl;
		//	system("pause");
			continue;
		}
		int u,v; cin >> u >> v;
		Link(u, v);
	}
} 
*/

Compilation message

rings.cpp: In function 'void dfs(int, int)':
rings.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < V[5][a].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'void build(int)':
rings.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for(int j = 0; j < V[5][i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for(int i = 0; i < V[5][rem[1]].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 16 ms 17492 KB Output is correct
3 Correct 18 ms 17648 KB Output is correct
4 Correct 10 ms 16852 KB Output is correct
5 Correct 13 ms 17108 KB Output is correct
6 Correct 16 ms 17492 KB Output is correct
7 Correct 13 ms 18168 KB Output is correct
8 Correct 14 ms 17236 KB Output is correct
9 Correct 21 ms 18844 KB Output is correct
10 Correct 22 ms 18888 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 16 ms 17492 KB Output is correct
3 Correct 18 ms 17648 KB Output is correct
4 Correct 10 ms 16852 KB Output is correct
5 Correct 13 ms 17108 KB Output is correct
6 Correct 16 ms 17492 KB Output is correct
7 Correct 13 ms 18168 KB Output is correct
8 Correct 14 ms 17236 KB Output is correct
9 Correct 21 ms 18844 KB Output is correct
10 Correct 22 ms 18888 KB Output is correct
11 Correct 28 ms 18892 KB Output is correct
12 Correct 33 ms 21064 KB Output is correct
13 Correct 49 ms 21752 KB Output is correct
14 Correct 26 ms 18408 KB Output is correct
15 Correct 27 ms 19504 KB Output is correct
16 Correct 21 ms 17868 KB Output is correct
17 Correct 22 ms 17916 KB Output is correct
18 Correct 127 ms 25420 KB Output is correct
19 Correct 24 ms 17936 KB Output is correct
20 Correct 58 ms 21036 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 16 ms 17492 KB Output is correct
3 Correct 18 ms 17648 KB Output is correct
4 Correct 10 ms 16852 KB Output is correct
5 Correct 13 ms 17108 KB Output is correct
6 Correct 16 ms 17492 KB Output is correct
7 Correct 13 ms 18168 KB Output is correct
8 Correct 14 ms 17236 KB Output is correct
9 Correct 21 ms 18844 KB Output is correct
10 Correct 22 ms 18888 KB Output is correct
11 Correct 28 ms 18892 KB Output is correct
12 Correct 33 ms 21064 KB Output is correct
13 Correct 49 ms 21752 KB Output is correct
14 Correct 26 ms 18408 KB Output is correct
15 Correct 27 ms 19504 KB Output is correct
16 Correct 21 ms 17868 KB Output is correct
17 Correct 22 ms 17916 KB Output is correct
18 Correct 127 ms 25420 KB Output is correct
19 Correct 24 ms 17936 KB Output is correct
20 Correct 58 ms 21036 KB Output is correct
21 Correct 72 ms 21828 KB Output is correct
22 Correct 104 ms 24828 KB Output is correct
23 Correct 140 ms 26980 KB Output is correct
24 Correct 306 ms 31928 KB Output is correct
25 Correct 206 ms 49100 KB Output is correct
26 Correct 1034 ms 59468 KB Output is correct
27 Correct 186 ms 26792 KB Output is correct
28 Correct 1230 ms 54852 KB Output is correct
29 Correct 726 ms 56972 KB Output is correct
30 Correct 243 ms 29372 KB Output is correct

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 16 ms 17492 KB Output is correct
3 Correct 18 ms 17648 KB Output is correct
4 Correct 10 ms 16852 KB Output is correct
5 Correct 13 ms 17108 KB Output is correct
6 Correct 16 ms 17492 KB Output is correct
7 Correct 13 ms 18168 KB Output is correct
8 Correct 14 ms 17236 KB Output is correct
9 Correct 21 ms 18844 KB Output is correct
10 Correct 22 ms 18888 KB Output is correct
11 Runtime error 54 ms 51264 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -