oj.uz

답안 #594938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594938 2022-07-13T07:27:55 Z 8e7 낙하산 고리들 (IOI12_rings) C++17
0 / 100
 4000 ms 94388 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<int, int>
#define ff first
#define ss second

struct DSU{
	int par[maxn], siz[maxn];
	void init(int n){
		for (int i = 1;i <= n;i++) par[i] = i, siz[i] = 1;
	}
	int find(int a){
		return a == par[a] ? a : (par[a] = find(par[a]));
	}
	bool Union(int a, int b){
		a = find(a), b = find(b);
		if (a == b) return 0;
		if (siz[a] < siz[b]) swap(a, b);
		par[b] = a;
		siz[a] += siz[b];
		return 1;
	}
};
struct graph{ //maintaining a graph of nodes with deg <= 2
	DSU d;
	int deg[maxn];
	int cycle = 0, ignore = -1, count = 0;
	bool good = 1;
	int maxdeg = 0;
	void addedge(int u, int v){
		debug("zisk");
		if (u == ignore || v == ignore) return;
		deg[u]++, deg[v]++;
		maxdeg = max(maxdeg, max(deg[u], deg[v]));
		if (maxdeg > 2) {
			good = 0;
			return;
		}
		debug("zisk");
		if (!d.Union(u, v)) {
			cycle++;	
			if (cycle > 1) good = 0;
			else count = d.siz[d.find(u)];
		}	
	}	
} g;
vector<int> adj[maxn];
vector<pii> ed;
int N;
void Init(int N_) {
	N = N_;
	g.d.init(N);
}
vector<graph> cand;
void Link(int A, int B) {
	adj[A].push_back(B);
	adj[B].push_back(A);
	ed.push_back({A, B});
	if (g.maxdeg < 3) {
		g.addedge(A, B);
		if (g.maxdeg >= 3) {
			if (g.deg[B] >= 3) swap(A, B);
			adj[A].push_back(A);
			for (int i:adj[A]) {
				graph tmp;
				tmp.d.init(N);
				tmp.ignore = i;
				for (auto p:ed) tmp.addedge(p.ff, p.ss);
				cand.push_back(tmp);
			}
			adj[A].pop_back();
		}
	} else {
		for (auto &t:cand){
			t.addedge(A, B);	
		}
	}
}

int CountCritical() {
	if (g.good) {
		if (g.cycle == 1) return g.count;
		else return N;
	} else {
		int ret = 0;
		for (auto &t:cand) {
			if (t.good) ret++;
		}
		return ret;
	}
}

Compilation message

rings.cpp: In member function 'void graph::addedge(int, int)':
rings.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
rings.cpp:45:3: note: in expansion of macro 'debug'
   45 |   debug("zisk");
      |   ^~~~~
rings.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
rings.cpp:53:3: note: in expansion of macro 'debug'
   53 |   debug("zisk");
      |   ^~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 35544 KB Output is correct
2 Incorrect 269 ms 94388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4034 ms 46136 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 35544 KB Output is correct
2 Incorrect 269 ms 94388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 35544 KB Output is correct
2 Incorrect 269 ms 94388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 35544 KB Output is correct
2 Incorrect 269 ms 94388 KB Output isn't correct
3 Halted 0 ms 0 KB -