이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr<<vars<<" = ";
string delim="";
(...,(cerr<<delim<<values,delim=", "));
cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxN=2e5+5; //make sure this is right
const int mod=1e9+7;
vector<int> graph[mxN];
int done[mxN],blue[mxN],never[mxN],deg[mxN];
void dfs(int at){
int t=0;
for(int &i:graph[at]){
if(blue[i]) t=1;
}
for(int &i:graph[at]){
if(never[i] || blue[i]) continue;
if(t){
never[i]=1;
dfs(i);
} else{
blue[i]=1;
dfs(i);
}
}
}
int main(){
cin.sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n; cin>>n;
for(int i=0;i<n;i++){
int a,b; cin>>a>>b;
graph[a].pb(b);
graph[b].pb(a);
deg[a]++;
deg[b]++;
}
queue<int> q;
for(int i=1;i<=n;i++){
if(deg[i]==1) q.push(i);
}
if(!sz(q)){
if(n%4){
cout<<-1<<"\n";
} else{
int ans=0;
blue[1]=1;
blue[graph[1][0]]=1;
dfs(graph[1][0]);
for(int i=1;i<=n;i++)
ans+=blue[i];
cout<<ans<<"\n";
}
return 0;
}
int ans=0;
while(!q.empty()){
int at=q.front();
q.pop();
done[at]=1;
ans++;
for(int &i:graph[at]){
if(never[i]) continue;
blue[i]=1;
for(int &j:graph[i]){
if(!done[j]){
done[j]=1;
for(int &k:graph[j]){
if(blue[k]) continue;
if(!never[k]){
for(int &u:graph[k]){
if(blue[u] || done[u]) continue;
deg[u]--;
if(!deg[u]){
cout<<-1<<"\n";
return 0;
}
if(deg[u]==1) q.push(u);
}
}
never[k]=1;
}
}
}
}
}
cout<<ans<<"\n";
}
# | 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... |