#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int n;
int m;
pii edges[100005];
vector<int> graf[100005];
int dsu[100005];
int finddsu(int x){
if(x == dsu[x])return x;
return dsu[x] = finddsu(dsu[x]);
}
int dist[100005];
void dfsdist(int x, int duz){
dist[x] = duz;
for(auto c:graf[x]){
if(dist[c])continue;
dfsdist(c, duz + 1);
}
}
ll ans = 1e9;
int z1,z2;
bool bio[100005][2][2];
ll dp[100005][2][2];
void dfs(int x, int y, int z, int cale){
if(z && (x == z1 || x == z2)){
bio[x][y][z] = 1;
dp[x][y][z] = 1e9;
return;
}
if(bio[x][y][z])return;
bio[x][y][z] = 1;
for(auto c:graf[x]){
if(c == cale)continue;
dfs(c,0,0,x);
dfs(c,0,1,x);
dfs(c,1,0,x);
dfs(c,1,1,x);
}
if(y == 0 && z == 0){
ll sum = 0;
bool doso = 0;
for(auto c:graf[x]){
if(c == cale)continue;
doso = 1;
sum += dp[c][0][0];
}
if(!doso){
dp[x][y][z] = 1e9;
return;
}
dp[x][y][z] = 1e9;
for(auto c:graf[x]){
if(c == cale)continue;
dp[x][y][z] = min(dp[x][y][z], sum - dp[c][0][0] + dp[c][0][1]);
}
}
if(y == 0 && z == 1){
ll sum = 0;
bool doso = 0;
for(auto c:graf[x]){
if(c == cale)continue;
doso = 1;
sum += dp[c][1][0];
}
if(!doso){
dp[x][y][z] = 1e9;
return;
}
dp[x][y][z] = 1e9;
for(auto c:graf[x]){
if(c == cale)continue;
dp[x][y][z] = min(dp[x][y][z], sum-dp[c][1][0]+dp[c][1][1]);
}
dp[x][y][z]++;
}
if(y == 1 && z == 0){
dp[x][y][z] = 0;
for(auto c:graf[x]){
if(c == cale)continue;
dp[x][y][z] += dp[c][0][0];
}
ll kurac =1e9;
dp[x][y][z] = min(dp[x][y][z], kurac);
}
if(y == 1 && z == 1){
dp[x][y][z] = 1;
for(auto c:graf[x]){
if(c == cale)continue;
dp[x][y][z] += dp[c][1][0];
}
ll kurac =1e9;
dp[x][y][z] = min(dp[x][y][z], kurac);
}
}
void resi(int f1, int f2){
z1 = f1;
z2 = f2;
ff(i,1,n)graf[i].clear();
ff(i,1,n){
if(edges[i].xx == f1 && edges[i].yy == f2)continue;
if(edges[i].yy == f1 && edges[i].xx == f2)continue;
graf[edges[i].xx].pb(edges[i].yy);
graf[edges[i].yy].pb(edges[i].xx);
}
ff(i,1,n){
ff(j,0,1){
ff(k,0,1){
bio[i][j][k] = dp[i][j][k] = 0;
}
}
}
dfs(1,0,1,0);
dfs(1,0,0,0);
ll sta = min(dp[1][0][1], dp[1][0][0]);
if(sta < 1e9)ans = min(ans, sta);
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
int idx = n;
ff(i,1,n)dsu[i] = i;
ff(i,1,n){
int x,y;
cin >> x >> y;
int p1 = finddsu(x);
int p2 = finddsu(y);
if(p1 == p2){
idx = i;
}
else{
graf[x].pb(y);
graf[y].pb(x);
dsu[p1] = p2;
}
edges[i] = {x,y};
}
dfsdist(edges[idx].xx, 1);
vector<int> braca;
int tmp = edges[idx].yy;
while(tmp != edges[idx].xx){
braca.pb(tmp);
for(auto c:graf[tmp]){
if(dist[c] < dist[tmp]){
tmp = c;
break;
}
}
}
braca.pb(tmp);
int m = braca.size();
ff(j,0,2){
resi(braca[j%m],braca[(j+1)%m]);
}
if(ans >= n+5)ans = -1;
cout << ans << "\n";
return 0;
}
Compilation message
Main.cpp: In function 'void resi(int, int)':
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
Main.cpp:129:5: note: in expansion of macro 'ff'
129 | ff(i,1,n)graf[i].clear();
| ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
Main.cpp:130:5: note: in expansion of macro 'ff'
130 | ff(i,1,n){
| ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
Main.cpp:136:5: note: in expansion of macro 'ff'
136 | ff(i,1,n){
| ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
Main.cpp:137:9: note: in expansion of macro 'ff'
137 | ff(j,0,1){
| ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
Main.cpp:138:13: note: in expansion of macro 'ff'
138 | ff(k,0,1){
| ^~
Main.cpp:139:44: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
139 | bio[i][j][k] = dp[i][j][k] = 0;
| ~~~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
Main.cpp:156:5: note: in expansion of macro 'ff'
156 | ff(i,1,n)dsu[i] = i;
| ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
Main.cpp:157:5: note: in expansion of macro 'ff'
157 | ff(i,1,n){
| ^~
Main.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
| ^
Main.cpp:188:5: note: in expansion of macro 'ff'
188 | ff(j,0,2){
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
142 ms |
21396 KB |
Output is correct |
| 6 |
Correct |
143 ms |
21128 KB |
Output is correct |
| 7 |
Correct |
172 ms |
18648 KB |
Output is correct |
| 8 |
Correct |
155 ms |
19276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 13 |
Incorrect |
3 ms |
2720 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
142 ms |
21396 KB |
Output is correct |
| 6 |
Correct |
143 ms |
21128 KB |
Output is correct |
| 7 |
Correct |
172 ms |
18648 KB |
Output is correct |
| 8 |
Correct |
155 ms |
19276 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 13 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 14 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 17 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 18 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 21 |
Incorrect |
3 ms |
2720 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
