oj.uz

Submission #807428

# Submission time Handle Problem Language Result Execution time Memory
807428 2023-08-04T17:18:13 Z rnl42 Passport (JOI23_passport) C++14
48 / 100
 2000 ms 64856 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

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;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

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

constexpr int INF = 1e9;

vector<pair<vector<int>,int>> tree;
int tree_shift = 0;

int N, Q;
vector<int> L, R;
vector<int> X;
vector<vector<int>> dp;

struct Adjacency {
    int itree, ivec = 0;
    Adjacency(int u) {
        itree = tree_shift+u;
        correctidx();
    }
    inline void correctidx() {
        while (itree != 0 && ivec >= tree[itree].first.size()) {
            ivec = 0;
            itree >>= 1;
        }
    }
    Adjacency begin() {
        return Adjacency(itree-tree_shift);
    }
    Adjacency end() {
        return Adjacency(-tree_shift);
    }
    void operator++() {
        ivec++;
        correctidx();
    }
    bool operator!=(const Adjacency& other) const {
        return itree != other.itree || ivec != other.ivec;
    }
    int operator*() const {
        return tree[itree].first[ivec];
    }
};

void bfs(vector<int>& dist) {
    vector<vector<int>> q(2*N+10);
    for (int i = 0; i < (int)dist.size(); i++) {
        if (dist[i] < INF) q[dist[i]].push_back(i);
    }
    for (int d = 0; d < (int)q.size(); d++) {
        for (int u : q[d]) {
            if (dist[u] != d) continue;
            for (int v : Adjacency(u)) {
                if (u == v) continue;
                if (dist[u]+1 < dist[v]) {
                    dist[v] = dist[u]+1;
                    q[dist[v]].push_back(v);
                }
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> N;
    L.resize(N), R.resize(N);
    tree_shift = 1<<__lg(2*N-1);
    tree.resize(2*tree_shift);
    for (int i = 0; i < N; i++) {
        cin >> L[i] >> R[i], L[i]--, R[i]--;
        for (int l = tree_shift+L[i], r = tree_shift+R[i]+1; l < r; l >>= 1, r >>= 1) {
            if (l&1) tree[l++].first.push_back(i);
            if (r&1) tree[--r].first.push_back(i);
        }
    }
    cin >> Q;
    X.resize(Q);
    for (int i = 0; i < Q; i++) {
        cin >> X[i], X[i]--;
    }
    vector<int> ddeb(N, INF);
    ddeb[0] = 0;
    bfs(ddeb);
    ddeb[0]++;

    vector<int> dfin(N, INF);
    dfin[N-1] = 0;
    bfs(dfin);
    dfin[N-1]++;

    vector<int> ans(N);
    for (int i = 0; i < N; i++) {
        ans[i] = ddeb[i]+dfin[i];
    }
    bfs(ans);
    for (int i = 0; i < N; i++) if (ans[i] >= INF) ans[i] = -1; else ans[i]--;
    for (int i = 0; i < Q; i++) {
        cout << ans[X[i]] << '\n';
    }
}

Compilation message

passport.cpp: In member function 'void Adjacency::correctidx()':
passport.cpp:53:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         while (itree != 0 && ivec >= tree[itree].first.size()) {
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Execution timed out 2079 ms 64856 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 12 ms 1108 KB Output is correct
17 Correct 2 ms 980 KB Output is correct
18 Correct 23 ms 1176 KB Output is correct
19 Correct 23 ms 1200 KB Output is correct
20 Correct 2 ms 980 KB Output is correct
21 Correct 5 ms 980 KB Output is correct
22 Correct 8 ms 980 KB Output is correct
23 Correct 19 ms 1108 KB Output is correct
24 Correct 11 ms 980 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 12 ms 1108 KB Output is correct
17 Correct 2 ms 980 KB Output is correct
18 Correct 23 ms 1176 KB Output is correct
19 Correct 23 ms 1200 KB Output is correct
20 Correct 2 ms 980 KB Output is correct
21 Correct 5 ms 980 KB Output is correct
22 Correct 8 ms 980 KB Output is correct
23 Correct 19 ms 1108 KB Output is correct
24 Correct 11 ms 980 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 13 ms 1184 KB Output is correct
28 Correct 3 ms 1108 KB Output is correct
29 Correct 3 ms 976 KB Output is correct
30 Correct 6 ms 980 KB Output is correct
31 Correct 10 ms 1108 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Execution timed out 2079 ms 64856 KB Time limit exceeded
5 Halted 0 ms 0 KB -