Submission #1235940

#TimeUsernameProblemLanguageResultExecution timeMemory
1235940lechaaPoklon (COCI17_poklon7)C++20
114 / 120
517 ms182520 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int long long vector<vector<int>> g; vector<pair<int, int>> v; void dfs(int k, int p){ for(int y = 0; y < g[k].size(); y++){ dfs(g[k][y], k); } if(p == -1) return; if(v[p].first == 0){ v[p].first = max(v[k].first, v[k].second)+1; }else{ v[p].second = max(v[k].first, v[k].second)+1; } } void dfs1(int k){ for(int y = 0; y < g[k].size(); y++){ v[g[k][y]].first = v[k].first-1; dfs1(g[k][y]); } } main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; g.resize(n+1); v.resize(n+1); vector<int> b(n+1); vector<vector<int>> sv(n+1); for(int i = 1; i <= n; i++){ int a, b; cin >> a >> b; if(a > 0){ g[i].push_back(a); }else{ sv[i].push_back(abs(a)); } if(b > 0){ g[i].push_back(b); }else{ sv[i].push_back(abs(b)); } } dfs(1, -1); v[1].first = max(v[1].first, v[1].second); dfs1(1); int low = 0; int top = 1e9; int ans = 0; vector<int> p(32); int c = 1; for(int y = 0; y <= 31; y++){ p[y] = c; c *= 2; } while(low <= top){ int mid = (low + top)/2; bool gg = true; for(int i = 1; i <= n; i++){ for(int y = 0; y < sv[i].size(); y++){ if(sv[i][y] > mid * p[min(31LL, v[i].first)]){ gg = false; } } } if(gg){ ans = mid; top = mid-1; }else{ low = mid+1; } } int j = ans; if(j == 0){ cout << j << "\n"; return 0; } string ns = ""; while(j > 0){ if(j%2 == 1){ ns += '1'; }else{ ns += '0'; } j/=2; } reverse(ns.begin(), ns.end()); j = max(v[1].first, v[1].second)+1; while(j--){ ns += '0'; } cout << ns << "\n"; return 0; }

Compilation message (stderr)

poklon.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   28 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...