oj.uz

Submission #805286

# Submission time Handle Problem Language Result Execution time Memory
805286 2023-08-03T14:47:54 Z thimote75 Railway Trip (JOI17_railway_trip) C++14
20 / 100
 2000 ms 3276 KB 
#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;


template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
	cout << ' ' << to_string(H);
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

struct Container {
    map<int, int> m;

    void insert(int height, int pos) {
        auto it = m.upper_bound(height);
        while (it != m.begin()) {
            it --;

            int h = (*it).first;
            m.erase(h);
            
            it = m.upper_bound(height);
        }

        m.insert({ height, pos });
    }

    int query (int height) {
        auto it = m.lower_bound(height);
        if (it == m.end()) return -1;

        return (*it).second;
    }
};

idata heights;

idata  left_road;
idata right_road;

int N, K, Q;

idata bfs (int start) {
    queue<int> q; 
    idata answer(N, 1e9);
    answer[start] = 0;
    q.push(start);

    while (q.size() != 0) {
        int curr = q.front(); q.pop();

        for (int next : { left_road[curr], right_road[curr] }) {
            if (next == -1) continue ;

            if (answer[next] != 1e9) continue ;
            q.push(next);
            answer[next] = answer[curr] + 1;
        }
    }

    return answer;
}

int main () {
    cin >> N >> K >> Q;

    heights.resize(N);
    for (int i = 0; i < N; i ++) cin >> heights[i];

    left_road.resize(N, -1);
    Container cnt;
    for (int i = 0; i < N; i ++) {
        left_road[i] = cnt.query(heights[i]);
        cnt.insert(heights[i], i);
    }

    cnt.m.clear();
    right_road.resize(N, -1);
    for (int i = N - 1; i >= 0; i --) {
        right_road[i] = cnt.query(heights[i]);
        cnt.insert(heights[i], i);
    }

    for (int q = 0; q < Q; q ++) {
        int a, b;
        cin >> a >> b;
        a --; b --;

        idata tA = bfs(a);
        idata tB = bfs(b);
        int res = 1e9;
        for (int i = 0; i < N; i ++)
            res = min(res, tA[i] + tB[i] - 1);
        
        cout << res << "\n";
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 46 ms 2460 KB Output is correct
3 Correct 50 ms 2500 KB Output is correct
4 Correct 50 ms 2700 KB Output is correct
5 Correct 43 ms 2540 KB Output is correct
6 Correct 45 ms 2636 KB Output is correct
7 Correct 50 ms 3024 KB Output is correct
8 Correct 105 ms 2492 KB Output is correct
9 Correct 90 ms 3224 KB Output is correct
10 Correct 101 ms 2740 KB Output is correct
11 Correct 104 ms 3204 KB Output is correct
12 Correct 110 ms 3276 KB Output is correct
13 Correct 99 ms 3164 KB Output is correct
14 Correct 104 ms 3196 KB Output is correct
15 Correct 114 ms 3204 KB Output is correct
16 Correct 92 ms 3168 KB Output is correct
17 Correct 50 ms 2832 KB Output is correct
18 Correct 50 ms 2840 KB Output is correct
19 Correct 51 ms 2872 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 2840 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 3196 KB Time limit exceeded
2 Halted 0 ms 0 KB -