oj.uz

Submission #95157

# Submission time Handle Problem Language Result Execution time Memory
95157 2019-01-27T18:21:31 Z updown1 popa (BOI18_popa) C++17
100 / 100
 92 ms 412 KB 
#include <popa.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, P)
#define ffa ffi ffj
#define s <<" "<<
//#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
//500,000,000 operations
const int MAXN = 1000;
//Global Variables
int solve(int N, int* l, int* r) {
    int par[MAXN];
    ffi l[i] = r[i] = par[i] = -1;
    int root = 0;
    For (i, 1, N) {
        /// start at i-1 and go up to the root
        /// going to be a right child or the root
        int at = i-1;
        if (!query(at, i, i, i)) {
            r[at] = i;
            par[i] = at;
            //w<< "added" s i s "to the right of" s at<<e;
        }
        else {
            while (at != root && query(par[at], i, i, i)) at = par[at];
            /// i is the parent of at
            if (at == root) {
                l[i] = at;
                par[at] = i;
                root = i;
                //w<< "made" s i s "the root"<<e;
            }
            else {
                /// replace the right child of the parent
                r[par[at]] = i;
                par[i] = par[at];
                par[at] = i;
                l[i] = at;
            }
        }
    }
    return root;
}

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 248 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Correct 10 ms 248 KB Output is correct
4 Correct 8 ms 248 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 376 KB Output is correct
2 Correct 72 ms 376 KB Output is correct
3 Correct 62 ms 328 KB Output is correct
4 Correct 79 ms 412 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 376 KB Output is correct
2 Correct 92 ms 324 KB Output is correct
3 Correct 43 ms 328 KB Output is correct
4 Correct 64 ms 328 KB Output is correct