#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define fastIO cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false);
#define mid ((l + r) / 2)
#define lChild ((index * 2) + 1)
#define rChild ((index * 2) + 2)
using namespace std;
ll dfs(vector<vector<ll> >& graph, vector<bool>& visited, vector<ll>& blues, vector<bool>& isBlue, ll numBlues, ll numVis, ll startIndex) {
if(numVis == graph.size()) {
for(auto el : isBlue) cout<<el<<" ";
cout<<" => "<<numBlues<<endl;
for(auto el : visited) cout<<el<<" ";
cout<<endl;
for(auto el : blues) cout<<el<<" ";
cout<<endl;
cout<<"====="<<endl;
for(auto el : blues) if(el != 1) return LLONG_MAX;
return numBlues;
}
visited[startIndex] = true;
bool canBlue = true;
for(auto el : graph[startIndex]) {
cout<<blues[el]<<" ";
canBlue &= blues[el] == 0;
}
cout<<" => "<<canBlue<<endl;
ll ans = LLONG_MAX;
for(auto el : graph[startIndex]) {
if(visited[el]) continue;
ans = min(ans, dfs(graph, visited, blues, isBlue, numBlues, numVis + 1, el));
}
if(!canBlue) {
visited[startIndex] = false;
return ans;
}
for(auto el : graph[startIndex]) blues[el]++;
for(auto el : graph[startIndex]) {
if(visited[el]) continue;
ans = min(ans, dfs(graph, visited, blues, isBlue, numBlues + 1, numVis + 1, el));
}
for(auto el : graph[startIndex]) blues[el]--;
visited[startIndex] = false;
return ans;
}
bool check(ll bls, vector<vector<ll> >& graph) {
for(int i = 0; i < graph.size(); i++) {
ll blues = 0;
for(auto el : graph[i]) {
// cout<<bls<<" "<<(1 << el)<<endl;
blues += (bls & (1 << el)) > 0;
}
if(blues != 1) return false;
}
return true;
}
void solve(ll _) {
ll n; cin>>n;
vector<vector<ll> > graph(n);
vector<ll> blues(n, 0);
vector<bool> isBlue(n, false);
vector<bool> visited(n, false);
for(int i = 0; i < n; i++) {
ll x, y; cin>>x>>y;
x--; y--;
graph[x].push_back(y);
graph[y].push_back(x);
}
ll num = 0;
/* ll ans = LLONG_MAX;
for(int i = 0; i < (1<<n); i++) {
if(check(i, graph)) ans = min(ans, (ll)__builtin_popcountll(i));
}*/
cout<<(ceil(n / 2))<<endl;
//cout<<dfs(graph, visited,blues, isBlue,0, 1 , 0)<<endl;
}
int main() {
fastIO
//freopen("file.in", "r", stdin);
//freopen("file.out", "w", stdout);
ll t = 0; solve(t);
}
Compilation message
Main.cpp: In function 'long long int dfs(std::vector<std::vector<long long int> >&, std::vector<bool>&, std::vector<long long int>&, std::vector<bool>&, long long int, long long int, long long int)':
Main.cpp:17:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | if(numVis == graph.size()) {
| ~~~~~~~^~~~~~~~~~~~~~~
Main.cpp: In function 'bool check(long long int, std::vector<std::vector<long long int> >&)':
Main.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i = 0; i < graph.size(); i++) {
| ~~^~~~~~~~~~~~~~
Main.cpp: In function 'void solve(long long int)':
Main.cpp:101:8: warning: unused variable 'num' [-Wunused-variable]
101 | ll num = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
