# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
578056 | NintsiChkhaidze | Poklon (COCI17_poklon7) | C++14 | 288 ms | 87376 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define s second
#define int ll
#define f first
using namespace std;
const int N = 1000005;
int a[N],b[N],cnt[N];
int comp(int a,int add1,int b,int add2){
int id1=0,id2=0;
for (int i = 0; i < 30; i++){
if (((1LL<<i)&a)) id1=i;
if (((1LL<<i)&b)) id2=i;
}
int len1 = id1+1+add1;
int len2 = id2+1+add2;
if (len1 > len2) return a;
if (len2 > len1) return b;
len1 -= min(add1,add2);
for (int i = 1; i <= len1; i++){
int a1,b1;
if (id1<0) a1=0;
else a1 = ((1LL<<id1)&a);
if (id2<0) b1=0;
else b1= ((1LL<<id2)&b);
id1--,id2--;
if (a1 && !b1) return a;
if (!a1 && b1) return b;
}
return a;
}
int dfs(int x){
int mx;
if (a[x] < 0 && b[x] < 0) {
mx=max(-a[x],-b[x]);
}else if (a[x] < 0){
int k =dfs(b[x]);
mx=comp(k,cnt[b[x]],-a[x],0);
if (mx==k) cnt[x]+=cnt[b[x]];
}else if (b[x]<0){
int k =dfs(a[x]);
mx=comp(k,cnt[a[x]],-b[x],0);
if (mx==k) cnt[x]+=cnt[a[x]];
}else{
int p = dfs(a[x]),q=dfs(b[x]);
mx=comp(p,cnt[a[x]],q,cnt[b[x]]);
if(mx==p) cnt[x]+=cnt[a[x]];
else cnt[x]+=cnt[b[x]];
}
cnt[x]++;
return mx;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n;
cin>>n;
for(int i = 1; i <= n; i++)
cin>>a[i]>>b[i];
int res = dfs(1);
bool z=0;
for (int i=30;i>=0;i--){
if (((1LL<<i)&res)) z=1,cout<<1;
else if (z) cout<<0;
}
if (z){
for (int i=1;i<=cnt[1];i++)
cout<<0;
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |