oj.uz

Submission #799457

# Submission time Handle Problem Language Result Execution time Memory
799457 2023-07-31T14:47:09 Z PixelCat Roller Coaster Railroad (IOI16_railroad) C++14
30 / 100
 94 ms 17008 KB 
#include "railroad.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200'000;

struct DSU {
    int p[MAXN + 10];
    void init() {
        memset(p, -1, sizeof(p));
    }
    int find(int n) {
        if(p[n] < 0) return n;
        return p[n] = find(p[n]);
    }
    void uni(int a, int b) {
        // cerr << a << " " << b << "\n";
        a = find(a); b = find(b);
        assert(a != b);
        p[b] = a;
    }
    bool same(int a, int b) {
        return find(a) == find(b);
    }
} dsu;

long long plan_roller_coaster(std::vector<int32_t> s, std::vector<int32_t> t) {
    int n = sz(s);
    vector<pii> vs, vt;
    For(i, 0, n - 1) {
        vs.eb(s[i], i + 1);
        vt.eb(t[i], i + 1);
    }
    sort(all(vs));
    sort(all(vt));
    int ptr = 0;
    vector<int> stk;
    stk.eb(0);
    dsu.init();
    for(auto &p:vs) {
        // cerr << "owo? " << p.F << " " << p.S << "\n";
        while(ptr < n && vt[ptr].F <= p.F) {
            stk.eb(vt[ptr].S);
            ptr++;
        }
        if(sz(stk) && !dsu.same(stk.back(), p.S)) {
            dsu.uni(stk.back(), p.S);
            stk.pop_back();
        } else if(sz(stk) >= 2 && !dsu.same(stk[sz(stk) - 2], p.S)) {
            dsu.uni(stk[sz(stk) - 2], p.S);
            swap(stk[sz(stk) - 1], stk[sz(stk) - 2]);
            stk.pop_back();
        } else {
            return 1;
        }
    }
    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1844 KB n = 2
2 Correct 2 ms 1876 KB n = 2
3 Correct 1 ms 1748 KB n = 2
4 Correct 1 ms 1844 KB n = 2
5 Correct 1 ms 1748 KB n = 2
6 Incorrect 1 ms 1876 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1844 KB n = 2
2 Correct 2 ms 1876 KB n = 2
3 Correct 1 ms 1748 KB n = 2
4 Correct 1 ms 1844 KB n = 2
5 Correct 1 ms 1748 KB n = 2
6 Incorrect 1 ms 1876 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16956 KB n = 199999
2 Correct 94 ms 15324 KB n = 199991
3 Correct 66 ms 15340 KB n = 199993
4 Correct 52 ms 12496 KB n = 152076
5 Correct 41 ms 8420 KB n = 93249
6 Correct 67 ms 14100 KB n = 199910
7 Correct 72 ms 14612 KB n = 199999
8 Correct 66 ms 14260 KB n = 199997
9 Correct 60 ms 13256 KB n = 171294
10 Correct 51 ms 12096 KB n = 140872
11 Correct 92 ms 14220 KB n = 199886
12 Correct 65 ms 14620 KB n = 199996
13 Correct 63 ms 14244 KB n = 200000
14 Correct 62 ms 14540 KB n = 199998
15 Correct 62 ms 14500 KB n = 200000
16 Correct 63 ms 14888 KB n = 199998
17 Correct 67 ms 15328 KB n = 200000
18 Correct 68 ms 14620 KB n = 190000
19 Correct 76 ms 17008 KB n = 177777
20 Correct 35 ms 8604 KB n = 100000
21 Correct 80 ms 15332 KB n = 200000
22 Correct 81 ms 15244 KB n = 200000
23 Correct 70 ms 15292 KB n = 200000

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1844 KB n = 2
2 Correct 2 ms 1876 KB n = 2
3 Correct 1 ms 1748 KB n = 2
4 Correct 1 ms 1844 KB n = 2
5 Correct 1 ms 1748 KB n = 2
6 Incorrect 1 ms 1876 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -