oj.uz

Submission #702881

# Submission time Handle Problem Language Result Execution time Memory
702881 2023-02-25T09:23:00 Z ecxx popa (BOI18_popa) C++17
37 / 100
 722 ms 316 KB 
    #include <bits/stdc++.h>
    #include "popa.h"
     
    using namespace std;
     
    int solve(int n,int* lc,int* rc) {
     
        vector<int> lp(1001, -1), rp(1001, -1), lupa(1001, -1), rupa(1001, -1), lch(1001, -1), rch(1001, -1);
     
        for (int i = 0; i < n; i++) {
     
            // find lp and rp !!
     
            int lo, hi, mid;
     
            lo=0;hi=i;
     
            while (lo < hi) {
                // accept 1s, reject 0s
                mid = (lo+hi)>>1;
     
                if (query(mid, i, i, i)) {
                    hi = mid;
                } else { // =0
                    lo = mid+1;
                }
     
            }
     
            lp[i] = lo-1;
     
            lo=i;hi=n-1;
     
            while (lo < hi) {
                // accept 1s, reject 0s
                mid = (lo+hi+1)>>1;
     
                if (query(i, mid, i, i)) {
                    lo = mid;
                } else { // =0
                    hi = mid-1;
                }
     
            }
     
            rp[i] = lo+1;
            
        }
     
        int ROOT;
        int pa;
     
        for (int i = 0; i < n; i++) if (lp[i]==-1 && rp[i]==n) {ROOT=i;}
     
        for (int i = 0; i < n; i++) {
            if (i==ROOT) continue;
            if (lp[i]==-1 && rp[i]==n && i != ROOT) {
                rupa[i] = ROOT;
                continue;
            }
            else if (lp[i]==-1) {
                rupa[i] = rp[i];
                continue;
            }
            else if (rp[i]==n) {
                lupa[i] = lp[i];
                continue;
            }
     
            // compare the two, i guess
     
            else if (rp[lp[i]] == rp[i]) { // go to the left lol
                lupa[i] = lp[i];
            } else {
                rupa[i] = rp[i];           
            }
     
        }
     
        for (int i = 0 ; i < n; i++) { // process left-parent in this order
            if (lupa[i]+1) {
                pa = lupa[i];
                while (rch[pa]+1) pa = rch[pa];
                rch[pa] = i;
            }
        }
        for (int i = n-1 ; i >= 0; i--) { // process right-parent in this order
            if (rupa[i]+1) {
                pa = rupa[i];
                while (lch[pa]+1) pa = lch[pa];
                lch[pa] = i;
            }
        }
     
        for (int i = 0; i < n; i++) {lc[i] = lch[i]; rc[i] = rch[i];}
        
        return ROOT;
     
    }

Compilation message

popa.cpp: In function 'int solve(int, int*, int*)':
popa.cpp:97:16: warning: 'ROOT' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |         return ROOT;
      |                ^~~~

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 208 KB Output is correct
2 Correct 44 ms 208 KB Output is correct
3 Correct 25 ms 208 KB Output is correct
4 Correct 48 ms 208 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 308 KB Output is correct
2 Correct 537 ms 316 KB Output is correct
3 Correct 430 ms 312 KB Output is correct
4 Runtime error 274 ms 316 KB Execution killed with signal 13
5 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 208 KB too many queries
2 Halted 0 ms 0 KB -