oj.uz

Submission #593794

# Submission time Handle Problem Language Result Execution time Memory
593794 2022-07-11T15:27:34 Z vovik Railway Trip 2 (JOI22_ho_t4) C++17
8 / 100
 2000 ms 52964 KB 
#include <bits/stdc++.h>

namespace IO {
    const int DPAIRSIZ = 1 << 10;
    char BB[DPAIRSIZ], *SS = BB, *TT = BB;

    inline char getcha() {
        return SS == TT && (TT = (SS = BB) + fread(BB, 1, DPAIRSIZ, stdin), SS == TT) ? EOF : *SS++;
    }

    template<typename T = int>
    inline T read() {
        T x = 0;
        int fu = 1;
        char c = getcha();
        while (c > 57 || c < 48) {
            if (c == 45) fu = -1;
            c = getcha();
        }
        while (c <= 57 && c >= 48) {
            x = x * 10 + c - 48;
            c = getcha();
        }
        x *= fu;
        return x;
    }

    template<typename T>
    inline void read(T &x) {
        x = 0;
        int fu = 1;
        char c = getcha();
        while (c > 57 || c < 48) {
            if (c == 45) fu = -1;
            c = getcha();
        }
        while (c <= 57 && c >= 48) {
            x = x * 10 + c - 48;
            c = getcha();
        }
        x *= fu;
    }

    template<typename T>
    inline void read(T *bg, T *ed) { while (bg != ed) read(*bg++); }

    inline void read(char &ch) {
        ch = getcha();
        while (ch <= 32) ch = getcha();
    }

    inline void read(char *s) {
        char ch = getcha();
        while (ch <= 32) ch = getcha();
        while (ch > 32) *s++ = ch, ch = getcha();
        *s = '\0';
    }

    inline void read(std::string &s) {
        char ch = getcha();
        while (ch <= 32) ch = getcha();
        while (ch > 32) s.push_back(ch), ch = getcha();
    }

    inline void sread(char *s) {
        char ch = getcha();
        while (ch < 32) ch = getcha();
        while (ch >= 32) *s++ = ch, ch = getcha();
        *s = '\0';
    }

    inline void pread(char *&s) {
        char ch = getcha();
        while (ch <= 32) ch = getcha();
        while (ch > 32) *s++ = ch, ch = getcha();
        *s = '\0';
    }

    inline void spread(char *&s) {
        char ch = getcha();
        while (ch < 32) ch = getcha();
        while (ch >= 32) *s++ = ch, ch = getcha();
        *s = '\0';
    }

    template<typename T, typename ...Args>
    inline void read(T &x, Args &...args) {
        read(x);
        read(args...);
    }

    char out[DPAIRSIZ], *Out = out;
#define flush() fwrite(out, 1, Out - out, stdout)

    inline void putcha(char x) {
        *Out++ = x;
        if (Out - out >= (DPAIRSIZ)) flush(), Out = out;
    }

    template<typename T>
    inline void fprint(T x) {
        if (x < 0) putcha(45), x = -x;
        if (x > 9) fprint(x / 10);
        putcha(x % 10 + 48);
    }

    inline void print() { putcha(10); }

    template<typename T>
    inline void print(T x) {
        fprint(x);
        putcha(10);
    }

    inline void print(char *ch) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(10);
    }

    inline void put(char *ch) { while (*ch != '\0') putcha(*(ch++)); }

    inline void print(const char *ch) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(10);
    }

    inline void put(const char *ch) { while (*ch != '\0') putcha(*(ch++)); }

    template<typename T, typename ...Args>
    inline void print(T x, Args ...args) {
        fprint(x);
        putcha(32);
        print(args...);
    }

    template<typename ...Args>
    inline void print(const char *ch, Args ...args) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(32);
        print(args...);
    }

    template<typename ...Args>
    inline void print(char *ch, Args ...args) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(32);
        print(args...);
    }

    template<typename T, typename ...Args>
    inline void printl(T x, Args ...args) {
        fprint(x);
        putcha(10);
        printl(args...);
    }

    template<typename ...Args>
    inline void printl(const char *ch, Args ...args) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(10);
        printl(args...);
    }

    template<typename ...Args>
    inline void printl(char *ch, Args ...args) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(10);
        printl(args...);
    }

    template<typename T>
    inline void sprint(T x) {
        fprint(x);
        putcha(32);
    }

    template<typename T, typename ...Args>
    inline void sprint(T x, Args ...args) {
        fprint(x);
        putcha(32);
        sprint(args...);
    }

    template<typename T>
    inline void sprint(T *bg, T *ed) { while (bg != ed) sprint(*bg++); }

    template<typename T>
    inline void print(T *bg, T *ed) {
        while (bg != ed) sprint(*bg++);
        putcha(10);
    }

    template<typename T>
    inline void printl(T *bg, T *ed) { while (bg != ed) print(*bg++); }

    class AutoFlush {
    public:
        ~AutoFlush() { flush(); }
    } __AutoFlush;
} // namespace IO
using namespace IO;

#define vc vector

#define nd node*
#define pnd pair<nd, nd>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vc<pll> vpll;
typedef vc<vll> vvll;
typedef vc<vpll> vvpll;

template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
    ll operator()(const ll a, const ll b) {
        return (a * b) % MOD;
    }
};


template<typename T>
inline void sort(T &a) {
    sort(a.begin(), a.end());
}

template<typename T>
inline void unique(T &a) {
    a.resize(unique(a.begin(), a.end()) - a.begin());
}

template<typename T>
inline void reverse(T &a) {
    reverse(a.begin(), a.end());
}

const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;

int d[2005][2005];

int main() {
    int n, k;
    read(n, k);
    int m;
    read(m);
    vc<pair<int, int>> straight, cursed;
    for (int i = 0; i < m; ++i) {
        int l, r;
        read(l, r);
        --l;
        --r;
        if (l <= r) straight.emplace_back(l, r);
        else cursed.emplace_back(l, r);
    }
    vc<pair<int, int>> go(n);
    {// updating for straight
        vc<vc<int>> add(n + 1);
        vc<vc<int>> del(n + 1);
        for (int i = 0; i < straight.size(); ++i) {
            int begin = straight[i].first;
            int end = min(straight[i].second + 1, straight[i].first + k);
            add[begin].push_back(straight[i].second);
            del[end].push_back(straight[i].second);
        }
        for (int i = 0; i < n; ++i) go[i] = {i, i};
        multiset<int> e;
        for (int i = 0; i < n; ++i) {
            for (auto x: del[i]) e.erase(e.find(x));
            for (auto x: add[i]) e.insert(x);
            if (!e.empty()) go[i].second = max(go[i].second, *e.rbegin());
        }
    }
    {// updating for cursed
        vc<vc<int>> add(n + 1);
        vc<vc<int>> del(n + 1);
        for (int i = 0; i < cursed.size(); ++i) {
            int begin = cursed[i].first;
            int end = max(cursed[i].second - 1, cursed[i].first - k);
            add[begin].push_back(cursed[i].second);
            if (end >= 0) del[end].push_back(cursed[i].second);
        }
        multiset<int> e;
        for (int i = n - 1; i >= 0; --i) {
            for (auto x: del[i]) e.erase(e.find(x));
            for (auto x: add[i]) e.insert(x);
            if (!e.empty()) go[i].first = min(go[i].first, *e.begin());
        }
    }
    for (int v = 0; v < n; ++v) {
        for (int to = 0; to < n; ++to) {
            d[v][to] = 1e9;
        }
    }

    for (int v = 0; v < n; ++v) {
        d[v][v] = 0;
        for (int i = go[v].first; i <= go[v].second; ++i) {
            d[v][i] = 1;
        }
    }
    for (int u = 0; u < n; ++u) {
        for (int v = 0; v < n; ++v) {
            for (int to = 0; to < n; ++to) {
                d[v][to] = min(d[v][to], d[v][u] + d[u][to]);
            }
        }
    }
    int q;
    read(q);
    while (q--) {
        int v, to;
        read(v, to);
        --v, --to;
        if (d[v][to] == 1e9) {
            cout << "-1\n";
            continue;
        }
        cout << d[v][to] << '\n';
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:263:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  263 |         for (int i = 0; i < straight.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~~
Main.cpp:280:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  280 |         for (int i = 0; i < cursed.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1876 KB Output is correct
2 Correct 29 ms 1996 KB Output is correct
3 Correct 33 ms 1876 KB Output is correct
4 Correct 28 ms 1876 KB Output is correct
5 Correct 29 ms 1876 KB Output is correct
6 Correct 29 ms 1876 KB Output is correct
7 Correct 25 ms 1748 KB Output is correct
8 Correct 31 ms 1876 KB Output is correct
9 Correct 30 ms 1876 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 32 ms 1888 KB Output is correct
12 Correct 29 ms 1888 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1876 KB Output is correct
2 Correct 29 ms 1996 KB Output is correct
3 Correct 33 ms 1876 KB Output is correct
4 Correct 28 ms 1876 KB Output is correct
5 Correct 29 ms 1876 KB Output is correct
6 Correct 29 ms 1876 KB Output is correct
7 Correct 25 ms 1748 KB Output is correct
8 Correct 31 ms 1876 KB Output is correct
9 Correct 30 ms 1876 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 32 ms 1888 KB Output is correct
12 Correct 29 ms 1888 KB Output is correct
13 Execution timed out 2081 ms 16212 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 131 ms 51808 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 42404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 247 ms 52964 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1876 KB Output is correct
2 Correct 29 ms 1996 KB Output is correct
3 Correct 33 ms 1876 KB Output is correct
4 Correct 28 ms 1876 KB Output is correct
5 Correct 29 ms 1876 KB Output is correct
6 Correct 29 ms 1876 KB Output is correct
7 Correct 25 ms 1748 KB Output is correct
8 Correct 31 ms 1876 KB Output is correct
9 Correct 30 ms 1876 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 32 ms 1888 KB Output is correct
12 Correct 29 ms 1888 KB Output is correct
13 Execution timed out 2081 ms 16212 KB Time limit exceeded
14 Halted 0 ms 0 KB -