#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return __lg(mask);}
// mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T& container, string separator = " ", string finish = "\n"){
for(auto item: container) cout << item << separator;
cout << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
// void MessageBoard(int i, int j){cout << j << ",";}
struct DSU{
int n;
vector<int> parent;
DSU(int _n){
n = _n;
parent.resize(n);
for(int i = 0; i<n; ++i) parent[i] = i;
}
int find_set(int u){return (u == parent[u]) ? u : (parent[u] = find_set(parent[u]));}
bool same_set(int u, int v){return find_set(u) == find_set(v);}
bool join_set(int u, int v){
u = find_set(u), v = find_set(v);
if (u != v){
parent[v] = u;
return true;
}
return false;
}
};
const int N = 1e4 + 69;
vector<int> graph[N];
vector<int> ver[N];
int color[N];
int untouched_cnt;
void dfs(int u, int p){
ver[u].push_back(u);
for(int v: graph[u]) if (v != p){
dfs(v, u);
for(int i: ver[v]) ver[u].push_back(i);
ver[v].clear();
}
if (ver[u].size() >= 60 && (untouched_cnt - ver[u].size() >= 60 || u == p)){
untouched_cnt -= ver[u].size();
for(int i = 0; i< ver[u].size(); ++i){
color[ver[u][i]] = i % 60;
}
ver[u].clear();
}
}
void Joi(int n, int m, int A[], int B[], ll X, int T) {
vector<pair<int, int>> edging(m);
for(int i = 0; i<m; ++i){
edging[i] = {A[i], B[i]};
if (edging[i].first > edging[i].second) swap(edging[i].first, edging[i].second);
}
sort(ALL(edging));
DSU mst(n);
for(pair<int, int> i: edging){
if (mst.join_set(i.first, i.second)){
int u = i.first, v = i.second;
graph[u].push_back(v);
graph[v].push_back(u);
}
}
untouched_cnt = n;
dfs(0, 0);
for(int i = 0; i<n; ++i) {
MessageBoard(i, GETBIT(X, color[i]));
}
}
// int main(void){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// int n = 150, m = 149;
// int A[m], B[m];
// for(int i = 0; i<m; ++i) {
// A[i] = i;
// B[i] = i + 1;
// }
// Joi(n, m, A, B, 69, 1);
// return 0;
// }
#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return __lg(mask);}
// mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T& container, string separator = " ", string finish = "\n"){
for(auto item: container) cout << item << separator;
cout << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
const int INF = 1e9 + 69;
// int tape[] = {1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
// int Move(int v){
// return tape[v];
// }
struct DSU{
int n;
vector<int> parent;
DSU(int _n){
n = _n;
parent.resize(n);
for(int i = 0; i<n; ++i) parent[i] = i;
}
int find_set(int u){return (u == parent[u]) ? u : (parent[u] = find_set(parent[u]));}
bool same_set(int u, int v){return find_set(u) == find_set(v);}
bool join_set(int u, int v){
u = find_set(u), v = find_set(v);
if (u != v){
parent[v] = u;
return true;
}
return false;
}
};
const int N = 1e4 + 69;
vector<int> graph[N];
vector<int> ver[N], shit[N];
int color[N];
int untouched_cnt;
void dfs(int u, int p){
ver[u].push_back(u);
for(int v: graph[u]) if (v != p){
dfs(v, u);
for(int i: ver[v]) ver[u].push_back(i);
ver[v].clear();
}
if (ver[u].size() >= 60 && (untouched_cnt - ver[u].size() >= 60 || u == p)){
untouched_cnt -= ver[u].size();
for(int i = 0; i< ver[u].size(); ++i){
color[ver[u][i]] = i % 60;
}
shit[u] = ver[u];
ver[u].clear();
}
}
bool dp[N];
int sum[N];
bool bit[60];
void go(int u, int p, int &cnt){
for(int v: graph[u]) if (v != p){
go(v, u, cnt);
if (dp[v]) {
dp[u] = 1;
sum[u] += sum[v] + 1;
}
}
}
void bobby(int u, int p){
for(int v: graph[u]) if (v != p && dp[v]){
bit[color[v]] = Move(v);
bobby(v, u);
}
if (u != p) Move(p);
}
ll Ioi(int n, int m, int A[], int B[], int P, int V, int T) {
vector<pair<int, int>> edging(m);
for(int i = 0; i<m; ++i){
edging[i] = {A[i], B[i]};
if (edging[i].first > edging[i].second) swap(edging[i].first, edging[i].second);
}
sort(ALL(edging));
DSU mst(n);
for(pair<int, int> i: edging){
if (mst.join_set(i.first, i.second)){
int u = i.first, v = i.second;
graph[u].push_back(v);
graph[v].push_back(u);
}
}
untouched_cnt = n;
dfs(0, 0);
bit[color[P]] = V;
for(int i = 0; i<n; ++i) {
int pos = -1;
for(int j = 0; j < shit[i].size(); ++j) if (shit[i][j] == P) pos = j;
if (pos == -1) continue;
pair<int, int> best = {INF, INF};
for(int j = 0; j + 59 < shit[i].size();++j)if (j <= pos && pos <= j + 59){
memset(dp, 0, sizeof dp); memset(sum, 0, sizeof sum);
for(int k = j; k <= j+59; ++k) dp[shit[i][k]] = 1;
go(P, P);
minimize(best, make_pair(sum[P], j));
}
memset(dp, 0, sizeof dp); memset(sum, 0, sizeof sum);
for(int k = best.second; k <= best.second+59; ++k) dp[shit[i][k]] = 1;
go(P, P);
bobby(P, P);
break;
}
ll X = 0;
for(int i = 0; i<60; ++i) if (bit[i]) X += MASK(i);
return X;
}
// int main(void){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// int n = 150, m = 149;
// int A[m], B[m];
// for(int i = 0; i<m; ++i) {
// A[i] = i;
// B[i] = i + 1;
// }
// cout << Ioi(n, m, A, B, 69, tape[69], 1) << "\n";
// return 0;
// }
Compilation message
Joi.cpp: In function 'void dfs(int, int)':
Joi.cpp:90:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 0; i< ver[u].size(); ++i){
| ~^~~~~~~~~~~~~~~
Ioi.cpp: In function 'void dfs(int, int)':
Ioi.cpp:95:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i = 0; i< ver[u].size(); ++i){
| ~^~~~~~~~~~~~~~~
Ioi.cpp: In function 'll Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:150:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for(int j = 0; j < shit[i].size(); ++j) if (shit[i][j] == P) pos = j;
| ~~^~~~~~~~~~~~~~~~
Ioi.cpp:155:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | for(int j = 0; j + 59 < shit[i].size();++j)if (j <= pos && pos <= j + 59){
| ~~~~~~~^~~~~~~~~~~~~~~~
Ioi.cpp:158:20: error: too few arguments to function 'void go(int, int, int&)'
158 | go(P, P);
| ^
Ioi.cpp:107:6: note: declared here
107 | void go(int u, int p, int &cnt){
| ^~
Ioi.cpp:164:16: error: too few arguments to function 'void go(int, int, int&)'
164 | go(P, P);
| ^
Ioi.cpp:107:6: note: declared here
107 | void go(int u, int p, int &cnt){
| ^~
