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;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define int long long
const int N = 1e5+5;
int n, dp[N][2][2], dp2[N][2][2][2][2], tr[N], dp3[N][2][2];
vector<int> adj[N], cyc;
bool inc[N], ins[N], vis[N];
void get_cyc(int u, int p) {
if (!cyc.empty())return;
if (ins[u]) {
cyc.pb(u);
int cur = tr[u];
inc[u] = true;
while (cur != u) {
cyc.pb(cur);
inc[cur] = true;
cur = tr[cur];
}
return;
}
if (vis[u])return;
vis[u] = ins[u] = true;
for (auto &v : adj[u]) {
if (v == p)continue;
tr[u] = v;
get_cyc(v, u);
}
ins[u] = false;
}
int sol2(int u, int p, int val, int pv) {
int &ret = dp[u][val][pv];
if (~ret)return ret;
ret = val;
if (!pv) {
int mn = -1e9;
int f, s;
bool fl = false, f2 = false, fx = false;
for (auto &v : adj[u]) {
if (v == p || inc[v])continue;
fx = true;
f = sol2(v, u, 0, val), s = sol2(v, u, 1, val);
if (f == s && f == int(1e9))return ret = int(1e9);
if (f == int(1e9)) {
if (fl)return ret = int(1e9);
ret += (mn == -1e9 ? 0 : mn);
mn = -1e9;
fl = true;
ret += s;
continue;
}
if (s == int(1e9)) {
ret += f;
continue;
}
if (f-s > mn) {
ret += (mn == -1e9 ? 0 : mn);
mn = f-s;
ret += s;
f2 = true;
} else {
ret += f;
}
}
if (!fx || (!fl && !f2))return ret = int(1e9);
} else {
for (auto &v : adj[u]) {
if (v == p || inc[v])continue;
ret += sol2(v, u, 0, val);
if (ret > int(1e9))return ret = int(1e9);
}
}
return ret;
}
int get(int u, int x, int val) {
int &ret = dp3[u][x][val];
if (~ret)return ret;
ret = 0;
bool fx = false;
if (!x) {
int mn = -1e9;
bool fl = false, f2 = false;
for (auto &v : adj[u]) {
if (inc[v])continue;
fx = true;
int f = sol2(v, u, 0, val), s = sol2(v, u, 1, val);
if (f == s && f == int(1e9))return ret = int(1e9);
if (f == int(1e9)) {
if (fl)return ret = int(1e9);
ret += (mn == -1e9 ? 0 : mn);
mn = -1e9;
fl = true;
ret += s;
continue;
}
if (s == int(1e9)) {
ret += f;
continue;
}
if (f-s > mn) {
ret += (mn == -1e9 ? 0 : mn);
mn = f-s;
ret += s;
f2 = true;
} else {
ret += f;
}
}
if (!fx)return ret = int(1e9);
if (!fl && !f2)return ret = int(1e9);
} else {
for (auto &v : adj[u]) {
if (inc[v])continue;
ret += sol2(v, u, 0, val);
if (ret > int(1e9))return ret = int(1e9);
}
}
return ret;
}
int sol(int i, int ls, int nls, int f, int nf) {
int &ret = dp2[i][ls][nls][f][nf];
if (~ret)return ret;
if (!i) {
int c1 = get(cyc[i], 0, 0) + sol(i+1, 0, 1, 0, 1);
c1 = min({c1, int(1e9), get(cyc[i], 1, 0) + sol(i+1, 0, 0, 0, 0)});
c1 = int(1e9);
int c2 = get(cyc[i], 0, 1) + 1 + sol(i+1, 1, 1, 1, 1);
c2 = min({c2, int(1e9), get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 0, 1, 0)});
return ret = min({int(1e9), c1, c2});
} else if (i == sz(cyc) - 1) {
if (f && ls)return ret = int(1e9);
if (nf+nls == 1)return ret = int(1e9);
if (nf + nls == 0) {
if (f + ls == 0) {
return ret = min(int(1e9), get(cyc[i], 0, 1) + 1);
} else {
return ret = min(int(1e9), 1 + get(cyc[i], 1, 1));
}
}
if (f + ls == 0)return ret = get(cyc[i], 0, 0);
return ret = get(cyc[i], 1, 0);
} else if (i == 1) {
if (ls) {
if (nf)return ret = min(int(1e9), get(cyc[i], 1, 0) + sol(i+1, 0, 1, f, nf));
int c1 = get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 1, f, 1);
int c2 = get(cyc[i], 1, 0) + sol(i+1, 0, 1, f, 0);
return ret = min({int(1e9), c1, c2});
}
if (nf)return ret = min(int(1e9), get(cyc[i], 0, 0) + sol(i+1, 0, 1, f, nf));
int c1 = get(cyc[i], 0, 1) + 1 + sol(i+1, 1, 1, f, 1);
c1 = min(c1, get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 0, f, 1));
int c2 = get(cyc[i], 0, 0) + sol(i+1, 0, 1, f, 0);
c2 = min(c2, get(cyc[i], 1, 0) + sol(i+1, 0, 0, f, 0));
return ret = min({int(1e9), c1, c2});
} else {
if (!nls) {
int c1 = get(cyc[i], ls, 1)+1+sol(i+1, 1, 1, f, nf);
c1 = min(c1, get(cyc[i], 1, 1)+1+sol(i+1, 1, ls, f, nf));
return ret = min(int(1e9), c1);
}
int c1 = get(cyc[i], ls, 0)+sol(i+1, 0, 1, f, nf);
c1 = min(c1, get(cyc[i], 1, 0)+sol(i+1, 0, ls, f, nf));
return ret = min(int(1e9), c1);
}
return ret;
}
signed main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
int u, v;
cin >> u >> v;
--u, --v;
adj[u].pb(v);
adj[v].pb(u);
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
dp[i][j][k] = dp3[i][j][k] = -1;
for (int l = 0; l < 2; l++) {
for (int m = 0; m < 2; m++) {
dp2[i][j][k][l][m] = -1;
}
}
}
}
}
get_cyc(0, 0);
int x = sol(0, 0, 0, 0, 0);
cout << (x > n ? -1 : x) << "\n";
}
Compilation message (stderr)
Main.cpp: In function 'long long int sol2(long long int, long long int, long long int, long long int)':
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:51:23: note: in expansion of macro 'int'
51 | if (f == s && f == int(1e9))return ret = int(1e9);
| ^~~
Main.cpp:51:22: error: expected ')' before 'long'
51 | if (f == s && f == int(1e9))return ret = int(1e9);
| ~ ^
| )
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:51:45: note: in expansion of macro 'int'
51 | if (f == s && f == int(1e9))return ret = int(1e9);
| ^~~
Main.cpp:51:44: error: expected ';' before 'long'
51 | if (f == s && f == int(1e9))return ret = int(1e9);
| ^
| ;
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:51:45: note: in expansion of macro 'int'
51 | if (f == s && f == int(1e9))return ret = int(1e9);
| ^~~
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:52:13: note: in expansion of macro 'int'
52 | if (f == int(1e9)) {
| ^~~
Main.cpp:52:12: error: expected ')' before 'long'
52 | if (f == int(1e9)) {
| ~ ^
| )
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:53:25: note: in expansion of macro 'int'
53 | if (fl)return ret = int(1e9);
| ^~~
Main.cpp:53:24: error: expected ';' before 'long'
53 | if (fl)return ret = int(1e9);
| ^
| ;
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:53:25: note: in expansion of macro 'int'
53 | if (fl)return ret = int(1e9);
| ^~~
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:60:13: note: in expansion of macro 'int'
60 | if (s == int(1e9)) {
| ^~~
Main.cpp:60:12: error: expected ')' before 'long'
60 | if (s == int(1e9)) {
| ~ ^
| )
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:73:40: note: in expansion of macro 'int'
73 | if (!fx || (!fl && !f2))return ret = int(1e9);
| ^~~
Main.cpp:73:39: error: expected ';' before 'long'
73 | if (!fx || (!fl && !f2))return ret = int(1e9);
| ^
| ;
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:73:40: note: in expansion of macro 'int'
73 | if (!fx || (!fl && !f2))return ret = int(1e9);
| ^~~
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:78:14: note: in expansion of macro 'int'
78 | if (ret > int(1e9))return ret = int(1e9);
| ^~~
Main.cpp:78:13: error: expected ')' before 'long'
78 | if (ret > int(1e9))return ret = int(1e9);
| ~ ^
| )
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:78:36: note: in expansion of macro 'int'
78 | if (ret > int(1e9))return ret = int(1e9);
| ^~~
Main.cpp:78:35: error: expected ';' before 'long'
78 | if (ret > int(1e9))return ret = int(1e9);
| ^
| ;
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:78:36: note: in expansion of macro 'int'
78 | if (ret > int(1e9))return ret = int(1e9);
| ^~~
Main.cpp: In function 'long long int get(long long int, long long int, long long int)':
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:96:23: note: in expansion of macro 'int'
96 | if (f == s && f == int(1e9))return ret = int(1e9);
| ^~~
Main.cpp:96:22: error: expected ')' before 'long'
96 | if (f == s && f == int(1e9))return ret = int(1e9);
| ~ ^
| )
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:96:45: note: in expansion of macro 'int'
96 | if (f == s && f == int(1e9))return ret = int(1e9);
| ^~~
Main.cpp:96:44: error: expected ';' before 'long'
96 | if (f == s && f == int(1e9))return ret = int(1e9);
| ^
| ;
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:96:45: note: in expansion of macro 'int'
96 | if (f == s && f == int(1e9))return ret = int(1e9);
| ^~~
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:97:13: note: in expansion of macro 'int'
97 | if (f == int(1e9)) {
| ^~~
Main.cpp:97:12: error: expected ')' before 'long'
97 | if (f == int(1e9)) {
| ~ ^
| )
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:98:25: note: in expansion of macro 'int'
98 | if (fl)return ret = int(1e9);
| ^~~
Main.cpp:98:24: error: expected ';' before 'long'
98 | if (fl)return ret = int(1e9);
| ^
| ;
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:98:25: note: in expansion of macro 'int'
98 | if (fl)return ret = int(1e9);
| ^~~
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:105:13: note: in expansion of macro 'int'
105 | if (s == int(1e9)) {
| ^~~
Main.cpp:105:12: error: expected ')' before 'long'
105 | if (s == int(1e9)) {
| ~ ^
| )
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:118:24: note: in expansion of macro 'int'
118 | if (!fx)return ret = int(1e9);
| ^~~
Main.cpp:118:23: error: expected ';' before 'long'
118 | if (!fx)return ret = int(1e9);
| ^
| ;
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:118:24: note: in expansion of macro 'int'
118 | if (!fx)return ret = int(1e9);
| ^~~
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:119:31: note: in expansion of macro 'int'
119 | if (!fl && !f2)return ret = int(1e9);
| ^~~
Main.cpp:119:30: error: expected ';' before 'long'
119 | if (!fl && !f2)return ret = int(1e9);
| ^
| ;
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:119:31: note: in expansion of macro 'int'
119 | if (!fl && !f2)return ret = int(1e9);
| ^~~
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:124:14: note: in expansion of macro 'int'
124 | if (ret > int(1e9))return ret = int(1e9);
| ^~~
Main.cpp:124:13: error: expected ')' before 'long'
124 | if (ret > int(1e9))return ret = int(1e9);
| ~ ^
| )
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:124:36: note: in expansion of macro 'int'
124 | if (ret > int(1e9))return ret = int(1e9);
| ^~~
Main.cpp:124:35: error: expected ';' before 'long'
124 | if (ret > int(1e9))return ret = int(1e9);
| ^
| ;
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:124:36: note: in expansion of macro 'int'
124 | if (ret > int(1e9))return ret = int(1e9);
| ^~~
Main.cpp: In function 'long long int sol(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:135:17: note: in expansion of macro 'int'
135 | c1 = min({c1, int(1e9), get(cyc[i], 1, 0) + sol(i+1, 0, 0, 0, 0)});
| ^~~
Main.cpp:10:13: error: expected '}' before 'long'
10 | #define int long long
| ^~~~
Main.cpp:135:17: note: in expansion of macro 'int'
135 | c1 = min({c1, int(1e9), get(cyc[i], 1, 0) + sol(i+1, 0, 0, 0, 0)});
| ^~~
Main.cpp:135:12: note: to match this '{'
135 | c1 = min({c1, int(1e9), get(cyc[i], 1, 0) + sol(i+1, 0, 0, 0, 0)});
| ^
Main.cpp:135:16: error: expected ')' before 'long'
135 | c1 = min({c1, int(1e9), get(cyc[i], 1, 0) + sol(i+1, 0, 0, 0, 0)});
| ~ ^
| )
Main.cpp:135:67: error: expected ')' before '}' token
135 | c1 = min({c1, int(1e9), get(cyc[i], 1, 0) + sol(i+1, 0, 0, 0, 0)});
| ~ ^
| )
Main.cpp:135:68: error: expected primary-expression before ')' token
135 | c1 = min({c1, int(1e9), get(cyc[i], 1, 0) + sol(i+1, 0, 0, 0, 0)});
| ^
Main.cpp:136:3: error: 'c1' was not declared in this scope; did you mean 'y1'?
136 | c1 = int(1e9);
| ^~
| y1
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:136:8: note: in expansion of macro 'int'
136 | c1 = int(1e9);
| ^~~
Main.cpp:10:13: error: expected primary-expression before 'long'
10 | #define int long long
| ^~~~
Main.cpp:138:17: note: in expansion of macro 'int'
138 | c2 = min({c2, int(1e9), get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 0, 1, 0)});
| ^~~
Main.cpp:10:13: error: expected '}' before 'long'
10 | #define int long long
| ^~~~
Main.cpp:138:17: note: in expansion of macro 'int'
138 | c2 = min({c2, int(1e9), get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 0, 1, 0)});
| ^~~
Main.cpp:138:12: note: to match this '{'
138 | c2 = min({c2, int(1e9), get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 0, 1, 0)});
| ^
Main.cpp:138:16: error: expected ')' before 'long'
138 | c2 = min({c2, int(1e9), get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 0, 1, 0)});
| ~ ^
| )
Main.cpp:138:71: error: expected ')' before '}' token
138 | c2 = min({c2, int(1e9), get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 0, 1, 0)});
| ~ ^
| )
Main.cpp: At global scope:
Main.cpp:138:72: error: expected unqualified-id before ')' token
138 | c2 = min({c2, int(1e9), get(cyc[i], 1, 1) + 1 + sol(i+1, 1, 0, 1, 0)});
| ^
Main.cpp:139:3: error: expected unqualified-id before 'return'
139 | return ret = min({int(1e9), c1, c2});
| ^~~~~~
Main.cpp:139:38: error: expected unqualified-id before ')' token
139 | return ret = min({int(1e9), c1, c2});
| ^
Main.cpp:140:2: error: expected declaration before '}' token
140 | } else if (i == sz(cyc) - 1) {
| ^
Main.cpp:140:4: error: expected unqualified-id before 'else'
140 | } else if (i == sz(cyc) - 1) {
| ^~~~
Main.cpp:152:4: error: expected unqualified-id before 'else'
152 | } else if (i == 1) {
| ^~~~
Main.cpp:165:4: error: expected unqualified-id before 'else'
165 | } else {
| ^~~~
Main.cpp:175:2: error: expected unqualified-id before 'return'
175 | return ret;
| ^~~~~~
Main.cpp:176:1: error: expected declaration before '}' token
176 | }
| ^
Main.cpp: In function 'long long int sol(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:137:55: warning: control reaches end of non-void function [-Wreturn-type]
137 | int c2 = get(cyc[i], 0, 1) + 1 + sol(i+1, 1, 1, 1, 1);
| ^