이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int n;
int fa[maxn][4];
int freq[maxn][3][4];
vector<int> adj[maxn][4];
int rt(int u, int j) {
if (fa[u][j]==u) return u;
return fa[u][j] = rt(fa[u][j], j);
}
void merge(int u, int v, int j) {
int U = rt(u, j), V = rt(v, j);
if (U!=V) {
for (int i=0;i<=2;i++) freq[V][i][j] += freq[U][i][j];
fa[U][j] = V;
}
if (adj[u][j].size()<=2) freq[V][adj[u][j].size()][j]--;
if (adj[v][j].size()<=2) freq[V][adj[v][j].size()][j]--;
adj[u][j].push_back(v); adj[v][j].push_back(u);
if (adj[u][j].size()<=2) freq[V][adj[u][j].size()][j]++;
if (adj[v][j].size()<=2) freq[V][adj[v][j].size()][j]++;
}
void Init(int32_t N) {
n = N;
for (int i=0;i<n;i++) for (int j=0;j<=3;j++) fa[i][j] = i, freq[i][0][j] = 1, freq[i][1][j] = freq[i][2][j] = 0;
}
vector<pair<int,int>> track;
bool start = false;
vector<pair<int,bool>> vec = {{-1, 1}};
vector<int> deadgrp = {-1};
bool now = true;
void Link(int32_t u, int32_t v) {
if (now) track.push_back({u, v});
int id = -1;
for (auto &[no, alive]:vec) {
id++;
if (u==no || v==no || !alive) continue;
merge(u, v, id);
if (!start && (adj[u][id].size()==3 || adj[v][id].size()==3)) {
start = true;
if (adj[v][id].size()==3) swap(u, v);
vec.clear();
for (int V:adj[u][id]) vec.push_back({V, 1});
vec.push_back({u, 1});
for (int i=0;i<n;i++) for (int j=0;j<=3;j++) adj[i][j].clear(), fa[i][j] = i, freq[i][0][j] = 1, freq[i][1][j] = freq[i][2][j] = 0;
deadgrp = {-1, -1, -1, -1};
now = false;
for (auto [x, y]:track) Link(x, y);
// if (u==2 && v==3) for (auto [x, y]:vec) cout << x << " " << y << endl;
now = true;
return;
}
int U = rt(u, id);
if (freq[U][1][id]!=2 && freq[U][0][id]!=1) {
if (start || (deadgrp[id]!=-1 && rt(deadgrp[id], id)!=U)) {
// cout << u << " " << v << " " << no << endl;
// cout << freq[U][1][id] << " " << id << endl;
alive = false;
continue;
}
deadgrp[id] = U;
}
if (adj[u][id].size()==4 || adj[v][id].size()==4) {
if (adj[v][id].size()==4) swap(u, v);
vec = {{u, 1}};
for (int i=0;i<n;i++) for (int j=0;j<=3;j++) adj[i][j].clear(), fa[i][j] = i, freq[i][0][j] = 1, freq[i][1][j] = freq[i][2][j] = 0;
deadgrp = {-1};
for (auto [x, y]:track) Link(x, y);
}
}
}
int32_t CountCritical() {
if (vec[0].first==-1) {
if (vec[0].second) return n;
return 0;
}
int ans = 0;
for (auto [trash, val]:vec) ans += val;
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |