Submission #408795

#TimeUsernameProblemLanguageResultExecution timeMemory
408795LptN21Poklon (COCI17_poklon7)C++14
120 / 120
469 ms150212 KiB
#include <bits/stdc++.h> using namespace std; #define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); #define FF first #define SS second #define pb push_back #define sz(x) (int)x.size() #define oo 1e18 #define eps 1e-9 #define PI acos(-1.0) #define lb lower_bound #define ub upper_bound typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> ii; const int N = 3e6+7, M=20+7; const int MOD = 1e9+7; int n, m, k, t; int val[N], d[N]; vector<int> adj[N]; void dfs(int u, int depth=0) { if(!sz(adj[u])) d[depth]=max(d[depth], val[u]); else dfs(adj[u][0], depth+1), dfs(adj[u][1], depth+1); } signed main() { //freopen("test.inp", "r", stdin); //freopen("test.out", "w", stdout); //fastIO; scanf("%d", &n); int u, v, r=n; memset(d, -1, sizeof d); for(int i=1;i<=n;i++) { scanf("%d%d", &u, &v); if(u<0) { val[++r]=-u; adj[i].pb(r); } else adj[i].pb(u); if(v<0) { val[++r]=-v; adj[i].pb(r); } else adj[i].pb(v); } dfs(1);vector<int> s; int ans=-1, ansdepth=-1; for(int i=1;i<N;i++) { if(d[i]==-1) continue; bool ok=0; if(ans<0) ok=1; else for(int j=1, u=2, r=(ans+d[i]-1)/d[i];j<=i-ansdepth;u<<=1, j++) if(u>=r) {ok=1;break;} if(ok) ans=d[i], ansdepth=i; } while(ans) s.pb(ans&1), ans>>=1; for(int i=sz(s)-1;i>=0;i--) printf("%d", s[i]); for(int i=0;i<ansdepth;i++) printf("0"); return 0; } /* stuff you should look for - int overflow, array bounds - special cases (n=1?) - do smth instead of do nothing and stay organized - WRITE STUFF DOWN - DONT JUST STICK ON ONE APPROACH */

Compilation message (stderr)

poklon.cpp: In function 'int main()':
poklon.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
poklon.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...