This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define ll long long
const long long inf=1e18;
const int MOD=998244353;
const int N=1e6+5;
vector<int> adj[N];
int n;
bool vis[N];
struct info{
int one;
int two;
int three;
int mx;
};
info dfs(int node,int par,int kr){
vis[node]=1;
info rt; rt.one=0; rt.two=0; rt.three=0; rt.mx=0;
int bad=0;
for(auto i:adj[node]){
if(i!=kr)bad++;
if(vis[i])continue;
info s=dfs(i,node,kr);
rt.one+=s.one;
rt.two+=s.two;
rt.three+=s.three;
rt.mx=max(rt.mx,s.mx);
}
if(bad<=1)rt.one+=1;
if(bad==2)rt.two=+1;
if(bad==3)rt.three+=1;
rt.mx=max(rt.mx,bad);
return rt;
}
void Init(int N){
n=N;
}
void Link(int A, int B){
adj[A].pb(B);
adj[B].pb(A);
}
int CountCritical(){
for(int i=1;i<=n;i++)vis[i]=0;
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)vis[j]=0;
vis[i]=1;
bool flag=1;
for(int j=1;j<=n;j++){
if(!vis[j]){
info yes=dfs(j,0,i);
if(yes.mx==0)continue;
if(yes.mx>=3 || yes.one!=2)flag=0;
}
}
if(flag){
ans++;
}
}
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... |