#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> adj[100001];
stack<int> st;bool ss = 0;
vector<int> cyc;int vis[100001];
void dfs(int i,int j){
if(vis[i]){
ss = 1;
cyc.push_back(i);
while(st.top()!=i){
cyc.push_back(st.top());
st.pop();
}
return ;
}
vis[i] = 1;
st.push(i);
for(auto e:adj[i]){
if(e.second!=j)dfs(e.first,e.second);
if(ss)return ;
}
if(ss)return ;
vis[i] = 0;st.pop();
}
bool imp[100001];
pair<int,int> dp[100001][4];
pair<int,int> solve(int i,int typ,int pr){
if(dp[i][typ]!=make_pair(-1,-1))return dp[i][typ];
if(typ==0){//it is blue eyed and have blue eyed friend
pair<int,int> val = {1,1};
for(auto j:adj[i]){
if(!imp[j.first]&&j.first!=pr){
val.first&=solve(j.first,2,i).first;
val.second+=solve(j.first,2,i).second;
}
}
return dp[i][typ] = val;
}if(typ==1){//it is blue eyed and don't have blue eyed friend
int c = 0 , sz = 0 , su = 0;
for(auto j:adj[i]){
if(!imp[j.first]&&j.first!=pr){
c+=solve(j.first,2,i).first;
su+=solve(j.first,2,i).second;
sz++;
}
}
pair<int,int> ed= {0,1000001};
for(auto j:adj[i]){
if(!imp[j.first]&&j.first!=pr){
if(c-solve(j.first,2,i).first==sz-1&&solve(j.first,0,i).first){
ed.first=1;
ed.second = min(ed.second,su-solve(j.first,2,i).second+solve(j.first,0,i).second+1);
}
}
}
return dp[i][typ] = ed;
}if(typ==2){//it is not blue eyed but have blue eyed friend
pair<int,int> val = {1,0};
for(auto j:adj[i]){
if(!imp[j.first]&&j.first!=pr){
val.first&=solve(j.first,3,i).first;
val.second+=solve(j.first,3,i).second;
}
}
return dp[i][typ] = val;
}if(typ==3){//it is not blue eyed and have not blue eyed friend
int c = 0 , sz = 0 , su = 0;
for(auto j:adj[i]){
if(!imp[j.first]&&j.first!=pr){
c+=solve(j.first,3,i).first;
su+=solve(j.first,3,i).second;
sz++;
}
}
pair<int,int> ed= {0,1000001};
for(auto j:adj[i]){
if(!imp[j.first]&&j.first!=pr){
if(c-solve(j.first,3,i).first==sz-1&&solve(j.first,1,i).first){
ed.first=1;
ed.second = min(ed.second,su-solve(j.first,3,i).second+solve(j.first,1,i).second);
}
}
}
return dp[i][typ] = ed;
}
}
pair<int,int> dp2[100001][4][4][4];
pair<int,int> ee(int i,int first,int togg,int la){
if(dp2[i][first][togg][la]!=make_pair(-1,-1))return dp2[i][first][togg][la];
if(la==1){
}
}
signed main(){
int n;cin>>n;
for(int i = 0;i<=n;i++){
dp[i][0] = {-1,-1};
dp[i][1] = {-1,-1};
dp[i][2] = {-1,-1};
dp[i][3] = {-1,-1};
}
for(int i = 0;i<n;i++){
int a,b;cin>>a>>b;
adj[a].push_back({b,i});
adj[b].push_back({a,i});
}
dfs(1,-1);
for(auto j:cyc){
imp[j] = 1;
}
for(auto j:cyc){
int x= solve(j,0,j).first;
x= solve(j,1,j).first;
x= solve(j,2,j).first;
x= solve(j,3,j).first;
}
{
int ch = solve(cyc[0],0,cyc[0]).first , su = solve(cyc[0],0,cyc[0]).second;
for(int i = 1;i<cyc.size()-1;i++){
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:113:13: warning: variable 'x' set but not used [-Wunused-but-set-variable]
113 | int x= solve(j,0,j).first;
| ^
Main.cpp:120:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int i = 1;i<cyc.size()-1;i++){
| ~^~~~~~~~~~~~~
Main.cpp:119:13: warning: unused variable 'ch' [-Wunused-variable]
119 | int ch = solve(cyc[0],0,cyc[0]).first , su = solve(cyc[0],0,cyc[0]).second;
| ^~
Main.cpp:119:49: warning: unused variable 'su' [-Wunused-variable]
119 | int ch = solve(cyc[0],0,cyc[0]).first , su = solve(cyc[0],0,cyc[0]).second;
| ^~
Main.cpp: In function 'std::pair<int, int> solve(int, int, int)':
Main.cpp:87:1: warning: control reaches end of non-void function [-Wreturn-type]
87 | }
| ^
Main.cpp: In function 'std::pair<int, int> ee(int, int, int, int)':
Main.cpp:94:1: warning: control reaches end of non-void function [-Wreturn-type]
94 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
