/*
This code belongs to Aadit Ambadkar
Date: 2022-02-06 21:31:34
Problem: poklon
*/
#include <bits/stdc++.h>
using namespace::std;
typedef long long ll;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define R0F(i, n) for (int i = n-1; i >= 0; i--)
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define MOD 1000000007
#define FF first
#define SS second
typedef __int128 lll;
const int MX = 2e6+3;
vector<int> adj[MX];
vector<lll> cwe(MX);
vector<lll> uw(MX, 0);
vector<ll> dpth(MX);
void gdep(int node, int cdepth, int parent) {
dpth[node]=cdepth;
for (auto i : adj[node]) {
if (i==parent) continue;
gdep(i, cdepth+1, node);
}
}
int main() {
fastio;
int n; cin >> n;
map<int, int> mi;
mi[1]=0;
FOR(i, 1, n+1) {
ll a, b; cin >> a >> b;
if (a>0) {
mi[a]=2*i-1;
} else {
uw[2*i-1] = -a;
}
if (b>0) {
mi[b]=2*i;
} else {
uw[2*i] = -b;
}
adj[mi[i]].pb(2*i-1);
adj[mi[i]].pb(2*i);
}
gdep(0, 0, 0);
// cout << "CP1" << endl;
vector<int> v(2*n+1);
F0R(i, 2*n+1) {
v[i]=i;
}
sort(v.begin(), v.end(), [&](int a, int b) {return dpth[a] > dpth[b];});
lll cd = dpth[v[0]];
int p = 0;
// cout << "CP2" << endl;
while (p<2*n+1 && dpth[v[p]]==cd) {
cwe[v[p]]=1;
p++;
}
// cout << "CP3" << endl;
lll k = 2;
cd--;
for (; p < 2*n+1;) {
while (p < 2*n+1 && dpth[v[p]]==cd) {
cwe[v[p]]=k;
p++;
}
cd--;
k*=2;
}
// cout << "CP4" << endl;
lll ans = 0;
F0R(i, 2*n+1) {
if (cwe[i]==0) {
// cout << i << " ";
continue;
}
if (dpth[v[0]]-dpth[i]>=32) continue;
ans = max(ans, (cwe[i]+uw[i]-1)/cwe[i]);
}
// cout << "\n";
// ans*=cwe[0];
vector<int> bits;
while (ans) {
bits.pb(ans%2);
ans/=2;
}
R0F(i, bits.size()) {
cout << bits[i];
}
cwe[0]/=2;
while (cwe[0]) {
cout << 0;
cwe[0]/=2;
}
cout << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
125508 KB |
Output is correct |
| 2 |
Correct |
53 ms |
125508 KB |
Output is correct |
| 3 |
Correct |
58 ms |
125440 KB |
Output is correct |
| 4 |
Correct |
57 ms |
125524 KB |
Output is correct |
| 5 |
Incorrect |
50 ms |
125548 KB |
Output isn't correct |
| 6 |
Correct |
49 ms |
125524 KB |
Output is correct |
| 7 |
Correct |
52 ms |
125452 KB |
Output is correct |
| 8 |
Correct |
51 ms |
125524 KB |
Output is correct |
| 9 |
Incorrect |
51 ms |
125612 KB |
Output isn't correct |
| 10 |
Correct |
51 ms |
125572 KB |
Output is correct |
| 11 |
Incorrect |
56 ms |
126516 KB |
Output isn't correct |
| 12 |
Incorrect |
71 ms |
126696 KB |
Output isn't correct |
| 13 |
Incorrect |
85 ms |
130552 KB |
Output isn't correct |
| 14 |
Incorrect |
119 ms |
135492 KB |
Output isn't correct |
| 15 |
Correct |
111 ms |
134088 KB |
Output is correct |
| 16 |
Incorrect |
298 ms |
158092 KB |
Output isn't correct |
| 17 |
Incorrect |
658 ms |
200872 KB |
Output isn't correct |
| 18 |
Incorrect |
661 ms |
202888 KB |
Output isn't correct |
| 19 |
Incorrect |
771 ms |
216576 KB |
Output isn't correct |
| 20 |
Incorrect |
952 ms |
239544 KB |
Output isn't correct |
