카테고리 없음
더럽고 추악한 선인장: 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)이 애초에 가능한가?
//행복!
코드가 좀 긴 이유가, 내가 간선선인장 판별법을 좀 이상하게 짜서 그렇다.
줄이려면 줄일 수 있을 것이다.