Submission #223742

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
223742	2020-04-16T09:25:44 Z	staniewzki	Parachute rings (IOI12_rings)	C++17	Compilation error	0 ms	0 KB

rings

clude<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
 
template<class T> int size(T && a) { return (int) a.size(); }
 
struct Graph {
	vector<int> rep, deg;
	int excluded = -1;
 
	int find(int x) {
		return rep[x] < 0 ? x : find(rep[x]);
	}
 
	int bicomp = -1;
	int get_cycle() {
		return -rep[find(bicomp)];
	}
 
	void join(int x, int y) {
		x = find(x), y = find(y);
		if(x == y) {
			if(bicomp == -1) bicomp = x;
			else bicomp = -2;
			return;
		}
        if(rep[x] > rep[y]) swap(x, y);
		rep[x] += rep[y];
		rep[y] = x;
	}
 
	int max_deg = 0;
	void add_edge(int a, int b) {
		if(a == excluded || b == excluded)
			return;
		max_deg = max(max_deg, ++deg[a]);
		max_deg = max(max_deg, ++deg[b]);
		join(a, b);
	}
 
	Graph(int n = 0, int e = -1) : rep(n, -1), deg(n), excluded(e) {}
};
 
int n;
vector<pair<int, int>> edges;
Graph graph;
vector<Graph> without;
 
void Init(int N) {
	n = N;
	graph = Graph(n);
}
 
void Link(int A, int B) {
	edges.emplace_back(A, B);
	if(graph.max_deg < 3) {
		graph.add_edge(A, B);
		if(graph.max_deg == 3) {
			if(graph.deg[A] != 3)
				swap(A, B);
 
			vector<int> crit = {A};
			for(auto &[u, v] : edges) {
				if(u == A) crit.emplace_back(v);
				if(v == A) crit.emplace_back(u);
			}
 
			for(int x : crit) {
				without.emplace_back(n, x);
				for(auto &[u, v] : edges)
					without.back().add_edge(v, u);		
			}
		}
	}
	else {
		for(auto &g : without)
			g.add_edge(A, B);
	}
}
 
int CountCritical() {
	if(graph.max_deg < 3) {
		if(graph.bicomp == -1) return n;
		if(graph.bicomp == -2) return 0;
		return graph.get_cycle();
	}
	else {
		int ret = 0;
		for(auto &g : without) {
			if(g.bicomp == -1 && g.max_deg < 3)
				ret++;
		}
		return ret;
	}
}

Compilation message

rings.cpp:1:1: error: 'clude' does not name a type
 clude<bits/stdc++.h>
 ^~~~~
rings.cpp:9:2: error: 'vector' does not name a type
  vector<int> rep, deg;
  ^~~~~~
rings.cpp: In member function 'int Graph::find(int)':
rings.cpp:13:10: error: 'rep' was not declared in this scope
   return rep[x] < 0 ? x : find(rep[x]);
          ^~~
rings.cpp: In member function 'int Graph::get_cycle()':
rings.cpp:18:11: error: 'rep' was not declared in this scope
   return -rep[find(bicomp)];
           ^~~
rings.cpp: In member function 'void Graph::join(int, int)':
rings.cpp:28:12: error: 'rep' was not declared in this scope
         if(rep[x] > rep[y]) swap(x, y);
            ^~~
rings.cpp:28:29: error: 'swap' was not declared in this scope
         if(rep[x] > rep[y]) swap(x, y);
                             ^~~~
rings.cpp:29:3: error: 'rep' was not declared in this scope
   rep[x] += rep[y];
   ^~~
rings.cpp: In member function 'void Graph::add_edge(int, int)':
rings.cpp:37:28: error: 'deg' was not declared in this scope
   max_deg = max(max_deg, ++deg[a]);
                            ^~~
rings.cpp:37:13: error: 'max' was not declared in this scope
   max_deg = max(max_deg, ++deg[a]);
             ^~~
rings.cpp: In constructor 'Graph::Graph(int, int)':
rings.cpp:42:33: error: class 'Graph' does not have any field named 'rep'
  Graph(int n = 0, int e = -1) : rep(n, -1), deg(n), excluded(e) {}
                                 ^~~
rings.cpp:42:45: error: class 'Graph' does not have any field named 'deg'
  Graph(int n = 0, int e = -1) : rep(n, -1), deg(n), excluded(e) {}
                                             ^~~
rings.cpp: At global scope:
rings.cpp:46:1: error: 'vector' does not name a type
 vector<pair<int, int>> edges;
 ^~~~~~
rings.cpp:48:1: error: 'vector' does not name a type
 vector<Graph> without;
 ^~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:56:2: error: 'edges' was not declared in this scope
  edges.emplace_back(A, B);
  ^~~~~
rings.cpp:60:13: error: 'struct Graph' has no member named 'deg'
    if(graph.deg[A] != 3)
             ^~~
rings.cpp:61:5: error: 'swap' was not declared in this scope
     swap(A, B);
     ^~~~
rings.cpp:63:4: error: 'vector' was not declared in this scope
    vector<int> crit = {A};
    ^~~~~~
rings.cpp:63:11: error: expected primary-expression before 'int'
    vector<int> crit = {A};
           ^~~
rings.cpp:64:23: error: unable to deduce 'auto&&' from 'edges'
    for(auto &[u, v] : edges) {
                       ^~~~~
rings.cpp:65:16: error: 'crit' was not declared in this scope
     if(u == A) crit.emplace_back(v);
                ^~~~
rings.cpp:65:16: note: suggested alternative: 'Init'
     if(u == A) crit.emplace_back(v);
                ^~~~
                Init
rings.cpp:66:16: error: 'crit' was not declared in this scope
     if(v == A) crit.emplace_back(u);
                ^~~~
rings.cpp:66:16: note: suggested alternative: 'Init'
     if(v == A) crit.emplace_back(u);
                ^~~~
                Init
rings.cpp:69:16: error: 'crit' was not declared in this scope
    for(int x : crit) {
                ^~~~
rings.cpp:69:16: note: suggested alternative: 'Init'
    for(int x : crit) {
                ^~~~
                Init
rings.cpp:70:5: error: 'without' was not declared in this scope
     without.emplace_back(n, x);
     ^~~~~~~
rings.cpp:71:24: error: unable to deduce 'auto&&' from 'edges'
     for(auto &[u, v] : edges)
                        ^~~~~
rings.cpp:77:17: error: 'without' was not declared in this scope
   for(auto &g : without)
                 ^~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:90:17: error: 'without' was not declared in this scope
   for(auto &g : without) {
                 ^~~~~~~