카테고리 없음

더럽고 추악한 선인장: BOJ 2111(PII)

wifilion 2024. 8. 29. 21:28

이 문제가 추악한 이유는 단 두 가지이다:

1. 간선 선인장인지 정점 선인장인지 명시를 하지 않았다. 아니 물론 간선 선인장이 디폴트라 해도, 많은 BCC 선인장

연습문제에서 선인장을 그냥 정점 선인장처럼 묘사하는 것은 분명히 문제가 있다

2. 내가 결국 C++로 O(N^2) 큰 수 곱셈 코드를 추가적으로 짜게 했다(물론 다항식 컨벌루션 O(NlogN)인 ^FFT^로도 가능하지만, 그러면 문제의 난이도가 턱없이 올라간다).

 

사실, 2번째가 많이 귀찮아서 PyPy3로 변환기 돌린다음에 제출했(었)다. 그러나 그냥 오늘 큰 수 곱셈 코드를 짜서 다시

통과시켰다. 이 문제, 메모리가 좀 짜다.

 

#include<bits/stdc++.h>
#define INF 20001
typedef long long int ll;
using namespace std;
ll dfsn[INF], N, M, cnt, r;// componentwise SN
vector<ll> a[INF];
vector<pair<ll, ll>> v;
stack<pair<ll, ll>> s;
vector<vector<pair<ll, ll>>> BCC;
map<pair<ll, ll>, ll> m;
bool visited[INF], cactus=true;
vector<ll> to_vector(int n){
	string s=to_string(n);
	vector<ll> v;
	for(ll i=s.length()-1;i>=0;i--){
		v.push_back(s[i]-'0');
	}
	return v;
}
void mul(vector<ll>& n, vector<ll>& m){
	vector<ll> ans(n.size()+m.size());
	int C=0; // Carry
	for(ll i=0;i<m.size();i++){
		for(ll j=0;j<n.size();j++){
			ll piv=m[i]*n[j];
			piv+=C;
			ans[i+j]+=piv;
			C=ans[i+j]/10;
			ans[i+j]%=10;
		}
		ll j=n.size();
		while(C>0){
			ans[i+j]+=C;
			C=ans[i+j]/10;
			ans[i+j]%=10;
		}
	} // 최초 할당 자리 
	n.resize(ans.size());
	n=ans;
}
ll DFS(ll now, ll par=0){
	dfsn[now]=++cnt;
	ll res=dfsn[now];
	for(ll i=0;i<a[now].size();i++){
		if(a[now][i]==par) continue;
		if(dfsn[now]>dfsn[a[now][i]]) s.push({now, a[now][i]});
		if(dfsn[a[now][i]]>0) res=min(res, dfsn[a[now][i]]);
		else{
			ll tmp=DFS(a[now][i], now);
			res=min(res, tmp);
			if(dfsn[now]<=tmp){
				vector<pair<ll, ll>> bcc;
				pair<ll, ll> p=make_pair(now, a[now][i]);
				while(s.top()!=p and !s.empty()){
					bcc.push_back(s.top());
					s.pop();
				}
				bcc.push_back(s.top());
				s.pop();
				BCC.push_back(bcc);
			} // BCC 추출 
		}
	}
	return res;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	for(ll i=0;i<M;i++){
		ll n;
		cin >> n;
		ll pre=0;
		for(ll j=0;j<n;j++){
			ll b;
			cin >> b;
			if(pre>0){
				a[pre].push_back(b);
				a[b].push_back(pre);
			}
			pre=b;
		}
	}
	for(ll i=1;i<=N;i++){
		if(!dfsn[i]){
			DFS(i);
			r++;
		}
	}
	if(r!=1){
		cout << "0";
		return 0;
	}
	vector<ll> mult;
	mult.push_back(1);
	for(ll i=0;i<BCC.size();i++){
		vector<pair<ll, ll>> bcc=BCC[i];
		map<int, int> visit;
		bool cycle=true;
		for(int j=0;j<bcc.size();j++){
			visit[bcc[j].first]++;
			visit[bcc[j].second]++;
		}
		for(auto iter=visit.begin();iter!=visit.end();iter++){
			if(iter->second<2){
				cycle=false;
			}
			else if(iter->second>2){
				cout << "0";
				return 0;
			}
		}
		if(cycle){
			vector<ll> size=to_vector(bcc.size()+1);
			mul(mult, size);
			vector<ll>().swap(size);
		}
	}
	bool len=false;
	for(int i=mult.size()-1;i>=0;i--){
		if(mult[i]>0) len=true;
		if(len) cout << mult[i];
	}
} // O(M)이 애초에 가능한가? 
//행복!

코드가 좀 긴 이유가, 내가 간선선인장 판별법을 좀 이상하게 짜서 그렇다.

줄이려면 줄일 수 있을 것이다.