Submission #1313250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313250		picrad	Poklon (COCI17_poklon7)	C++20	0 / 120	1097 ms	327680 KiB

poklon

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef double dbl;
typedef pair<ll,ll> pii;
 
const int maxn = 1e6+5,MOD = 1e9+7;
ll N,ans,par[maxn];
pii A[maxn];

bool p(int i, bool fi){
  if(fi) return (A[i].fi < 0);
  return A[i].se < 0;
}

string to_binary(ll x){
  if(x == 1)return "1";
   return to_binary(x/2) + (x % 2 == 0? "0" : "1");
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N;
  queue<ll> q;
  for(int i = 1; i <= N; i++) {
    cin >> A[i].fi >> A[i].se;
    if(A[i].fi <= 0 && A[i].se <= 0){
      q.push(i);
    }
    ans += max(0LL,-A[i].fi);
    ans += max(0LL,-A[i].se);
    if(A[i].fi > 0)par[A[i].fi] = i;
    if(A[i].se > 0)par[A[i].se] = i;
  }
  while(!q.empty()){
    ll x = q.front();
    q.pop();
    if(x == 0)continue;
    ll u = A[x].fi,v = A[x].se;
    
    if(u < v){
      ans += v-u;
      v = u;
    }else if ( v < u){
      ans += u-v;
      u = v;
    }
    
    if(x ==  A[par[x]].fi) A[par[x]].fi = u + v;
    else A[par[x]].se = u+v;
    if(p(par[x], (x ==  A[par[x]].fi ? 0 : 1))) q.push(par[x]);
  }
  cout << to_binary(ans) << endl;
}

• Subtask 1: 0 / 120