# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
const int N = 1e6 + 5;
int n,x[N],y[N],le_[N],ri_[N], sumw[N],lew[N],riw[N],cursz = 0;
string ans;
vector <pii > xx;
int mx,lvl[N],par[N],canadd[N];
vector <int> to_binary(int x) {
vector <int> v;
while (x > 0) {
v.pb(x % 2);
x /= 2;
}
reverse(v.begin(),v.end());
return v;
}
void updanss(int pw, int val) {
vector <int> vv = to_binary(val);
string ss = "";
for (int i = 0; i < vv.size(); i++) {
if (vv[i] == 1) ss += "1";
else ss += "0";
}
for (int i = 0; i < pw; i++) {
ss += "0";
}
if (vv.size() + pw > cursz) {
cursz = vv.size() + pw;
ans = ss;
}
else {
ans = max(ans, ss);
}
}
void updans(int pw, int val) {
vector <int> vv = to_binary(val);
int sz = log2(val) + 1;
if (sz != vv.size()) {
//cout<<val<<" "<<log2(val)<<endl;
exit(0);
}
if (sz + pw < cursz) {
return ;
}
if (sz + pw > cursz) {
cursz = sz + pw;
xx.clear();
}
xx.pb({pw,val});
}
void dfs(int node) {
if (node == 1) lvl[node] = 0;
else
lvl[node] = lvl[par[node]] + 1;
if (le_[node]) dfs(le_[node]);
else {
int lv = lvl[node] + 1;
updans(lv,lew[node]);
}
if (ri_[node]) dfs(ri_[node]);
else {
int lv = lvl[node] + 1;
updans(lv,riw[node]);
}
}
signed main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for (int i = 1; i <= n; i++) {
cin>>x[i]>>y[i];
}
for (int i = 1; i <= n; i++) {
if (x[i] > 0) {
le_[i] = x[i];
par[x[i]] = i;
} else lew[i] = -x[i];
if (y[i] > 0) {
ri_[i] = y[i];
par[y[i]] = i;
}
else riw[i] = -y[i];
}
dfs(1);
for (int i = 0; i < xx.size(); i++) {
updanss(xx[i].f, xx[i].s);
}
cout<<ans;
}
Compilation message
poklon.cpp: In function 'void updanss(int, int)':
poklon.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int i = 0; i < vv.size(); i++) {
| ~~^~~~~~~~~~~
poklon.cpp:31:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
31 | if (vv.size() + pw > cursz) {
| ~~~~~~~~~~~~~~~^~~~~~~
poklon.cpp: In function 'void updans(int, int)':
poklon.cpp:42:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | if (sz != vv.size()) {
| ~~~^~~~~~~~~~~~
poklon.cpp: In function 'int main()':
poklon.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i = 0; i < xx.size(); i++) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
4 ms |
852 KB |
Output is correct |
| 12 |
Correct |
5 ms |
904 KB |
Output is correct |
| 13 |
Correct |
22 ms |
2944 KB |
Output is correct |
| 14 |
Correct |
47 ms |
5804 KB |
Output is correct |
| 15 |
Correct |
60 ms |
3516 KB |
Output is correct |
| 16 |
Correct |
155 ms |
16024 KB |
Output is correct |
| 17 |
Correct |
357 ms |
35504 KB |
Output is correct |
| 18 |
Correct |
373 ms |
37564 KB |
Output is correct |
| 19 |
Correct |
452 ms |
38320 KB |
Output is correct |
| 20 |
Correct |
440 ms |
90264 KB |
Output is correct |
