oj.uz

Submission #335327

# Submission time Handle Problem Language Result Execution time Memory
335327 2020-12-12T00:20:54 Z gmyu Editor (BOI15_edi) C++14
100 / 100
 973 ms 30524 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 16 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 18 ms 748 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 14 ms 876 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 17 ms 876 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 29676 KB Output is correct
2 Correct 836 ms 29640 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 9452 KB Output is correct
2 Correct 515 ms 10976 KB Output is correct
3 Correct 785 ms 23148 KB Output is correct
4 Correct 835 ms 29676 KB Output is correct
5 Correct 830 ms 30280 KB Output is correct
6 Correct 817 ms 27632 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 16 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 18 ms 748 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 14 ms 876 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 17 ms 876 KB Output is correct
10 Correct 853 ms 29676 KB Output is correct
11 Correct 836 ms 29640 KB Output is correct
12 Correct 434 ms 9452 KB Output is correct
13 Correct 515 ms 10976 KB Output is correct
14 Correct 785 ms 23148 KB Output is correct
15 Correct 835 ms 29676 KB Output is correct
16 Correct 830 ms 30280 KB Output is correct
17 Correct 817 ms 27632 KB Output is correct
18 Correct 847 ms 18424 KB Output is correct
19 Correct 855 ms 18336 KB Output is correct
20 Correct 973 ms 28908 KB Output is correct
21 Correct 830 ms 29560 KB Output is correct
22 Correct 865 ms 30524 KB Output is correct