oj.uz

Submission #335323

# Submission time Handle Problem Language Result Execution time Memory
335323 2020-12-12T00:17:07 Z gmyu Editor (BOI15_edi) C++14
100 / 100
 966 ms 30572 KB 
/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define sz(x) (int)(x).size()
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 300007
#define MAXE 100007

/// code from USACO examples
void setIO(string name) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;

int N;
int a[MAXV], lev[MAXV];

#define MAXLCALOG 20
int anc[MAXV][MAXLCALOG];
int getP(int curr, int wantedDepth) {   /// reach wanted depth
    if(lev[curr] <= wantedDepth) return curr;
    for(int k = MAXLCALOG - 1; k>= 0; k--) {
        while(lev[anc[curr][k]] > wantedDepth) {
            curr = anc[curr][k];
        }
    }
    if(lev[curr] <= wantedDepth) return curr;
    return anc[curr][0];
}

int main() {
    debug = true; submit = false;
    if(submit) setIO("Editor");

    int i, j, k;

    cin >> N ;
    a[0] = 0;
    for(i=1; i <= N; i++) {
        cin >> a[i];
        if(a[i] > 0) {
            lev[i] = 0;
            cout << a[i] << endl;
        } else {
            lev[i] = -a[i];
            j = getP(i - 1, lev[i] - 1);
            k = getP(j - 1, lev[i] - 1);
            anc[i][0] = k;
            for(j = 1; j < MAXLCALOG; j++)
                    anc[i][j] = anc[anc[i][j-1]][j-1];
            k = getP(i, 0);
            cout << a[k] << endl;
        }
    }

}

Compilation message

edi.cpp: In function 'void setIO(std::string)':
edi.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
edi.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   42 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 19 ms 620 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 15 ms 876 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 17 ms 876 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 14 ms 876 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 846 ms 28164 KB Output is correct
2 Correct 823 ms 28140 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 8424 KB Output is correct
2 Correct 516 ms 10988 KB Output is correct
3 Correct 788 ms 23084 KB Output is correct
4 Correct 827 ms 29804 KB Output is correct
5 Correct 843 ms 30572 KB Output is correct
6 Correct 789 ms 27628 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 19 ms 620 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 15 ms 876 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 17 ms 876 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 14 ms 876 KB Output is correct
10 Correct 846 ms 28164 KB Output is correct
11 Correct 823 ms 28140 KB Output is correct
12 Correct 414 ms 8424 KB Output is correct
13 Correct 516 ms 10988 KB Output is correct
14 Correct 788 ms 23084 KB Output is correct
15 Correct 827 ms 29804 KB Output is correct
16 Correct 843 ms 30572 KB Output is correct
17 Correct 789 ms 27628 KB Output is correct
18 Correct 836 ms 18412 KB Output is correct
19 Correct 836 ms 18412 KB Output is correct
20 Correct 966 ms 28900 KB Output is correct
21 Correct 821 ms 29804 KB Output is correct
22 Correct 830 ms 30316 KB Output is correct