제출 #1140412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140412		sher	Toll (BOI17_toll)	C++20	100 / 100	1806 ms	6944 KiB

toll

#include <iostream>
#include "bits/stdc++.h"
//#include <memory>  // For std::unique_ptr

using namespace std;

typedef long long ll;

#define  range(i, a, b) for(int (i) = a; (i) < (b); (i)++)
//#define int long long
#define mod 998244353
//#define mod 1000000007
//#define mod 998244853
//#define mod 4294967296
#define infinity 999999999
//#define infinity 99
//#define infinity 999999999999999
//#define infinity LONG_LONG_MAX
#define yes "yes"
#define no "no"
#define No "No"
#define Yes "Yes"
#define YES "YES"
#define NO "NO"
#define all(x) x.begin(), x.end()


// TREE OF 11 edges 11 1 2 1 3 1 4 2 5 3 6 6 9 3 7 7 10 7 11 4 8
void print() {
    cout << "\n";
}

void print(const string &s) {
    cout << s << '\n';
}

void print(double x) {
    cout << x << '\n';
}

void print(int a) {
    cout << a << '\n';
}

void print(pair<int, int> p) {
    cout << "(" << p.first << ", " << p.second << ")";
}

void print(int A[], int N) {
    range(a, 0, N) cout << A[a] << ' ';
    cout << '\n';
}

void print(bool A[], int N) {
    range(a, 0, N) cout << A[a] << ' ';
    cout << '\n';
}

void print(const vector<int> &v, int length) {
    for (int x: v) {
        cout << x << ' ';
        length--;
        if (length < 0) break;
    }
    cout << '\n';
}

void print(const vector<int> &v) {
    for (int x: v) cout << x << ' ';
    cout << '\n';
}

void print(const vector<string> &v) {
    for (const string &x: v) cout << x << '\n';
    cout << "\n\n\n";
}

void print(const vector<bool> &v) {
    for (bool x: v) cout << x << ' ';
    cout << '\n';
}

void print(const vector<vector<int>> &v) {
    for (const auto &x: v) {
        print(x);
    }
}

void print(const vector<pair<int, int>> &v) {
    for (auto it: v) {
        print(it);
        cout << ' ';
    }
    cout << "\n";
}

void print(const map<int, int> &mp) {
    cout << "{";
    for (auto it: mp) cout << it.first << ": " << it.second << ", ";
    cout << "}\n";
}

void print(pair<int, int> A[], int N) {
    range(a, 0, N) {
        cout << "(" << A[a].first << ", " << A[a].second << ") ";
    }
    cout << '\n';
}

void print(const multiset<int> &st) {
    for (int i: st) cout << i << ' ';
    cout << '\n';
}

void print(const multiset<pair<int, int>> &st) {
    for (auto i: st) {
        print(i);
        cout << ' ';
    }
    cout << '\n';
}

void print(const set<int> &st) {
    for (int i: st) cout << i << ' ';
    cout << '\n';
}

void print(const unordered_set<int> &st) {
    for (int i: st) cout << i << ' ';
    cout << '\n';
}

void print(queue<int> q) {
    for (size_t i = 0; i < q.size(); i++) {
        cout << q.front() << ' ';
        q.push(q.front());
        q.pop();
    }
    print();
}

void print(const map<pair<int, int>, int> &mp) {
    cout << "{";
    for (auto it: mp) cout << '(' << it.first.first << ", " << it.first.second << ")" << ": " << it.second << ", ";
    cout << "}\n";
}

void print(pair<int, pair<int, int>> p) {
    cout << "(" << p.first << ", ";
    print(p.second);
    print(")");
}

long long power(long long x, int y, int p) {
    if (y == 0) return 1;
    long long res = 1;
    x = x % p;
    if (x == 0) return 0;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

long long multiply_mod(long long a, long long b) {
    long long res = 0;
    a %= mod;
    while (b) {
        if (b & 1)
            res = (res + a) % mod;
        a = (2 * a) % mod;

        b >>= 1;
    }
    return res;
}

int get_digit_sum(int x) {
    int ans = 0;
    while (x) {
        ans += (1);
        x /= 10;
    }
    return ans;
}

int sher() {
    int x;
    cin >> x;
    return x;
}


string read() {
    string s;
    cin >> s;
    return s;
}

vector<int> read_vector(int len) {
    vector<int> temp(len);
    range(a, 0, len) cin >> temp[a];
    return temp;
}

int inverse(int x, int p) {
    return power(x, p - 2, p);
}

int random_int() {
    int a = rand(), b = rand(), c = rand();
    return a * b + c;
}

int random_between(int l, int r) {
    if (r == l) return r;
    return (random_int() % (r - l)) + l;
}

int ceil(int a, int b) {
    int ans = a / b;
    if (a % b != 0) ans++;
    return ans;
}

pair<bool, int> my_sqrt(int x) {
    int p = (int) sqrt(x);
    int ans = -1;
    range(i, -5, 5) {
        int c = p + i;
        if (c < 0) continue;
        if (c * c == x) return {true, c};
        if (c * c <= x) ans = c;
    }
    return {false, ans};
}

vector<int> fact;

int binomial(int n, int r) {
    if (n < 0 || r < 0) return 0;
    if (r > n) return 0;
    if (r == n) return 1;
    int num = fact[n];
    int den = fact[r] * fact[n - r];
    den %= mod;
    den = inverse(den, mod);
    return ((num * den) % mod);
}

void factorials(int MAXN) {
    fact.push_back(1);
    range(a, 1, MAXN) fact.push_back((fact.back() * a) % mod);
}

vector<int> spf;

void sieve(int MAXN) {
    spf.resize(MAXN);
    spf[1] = 1;
    for (int i = 2; i < MAXN; i++)
        spf[i] = i;
    for (int i = 4; i < MAXN; i += 2)
        spf[i] = 2;

    for (int i = 3; i * i < MAXN; i++) {
        if (spf[i] == i) {
            for (int j = i * i; j < MAXN; j += i)
                if (spf[j] == j)
                    spf[j] = i;
        }
    }
}


vector<int> get_divisors(int x) {

    if (x == 1) return {1};
    int p = spf[x];
    auto prev = get_divisors(x / p);
    vector<int> ans;
    for (int d: prev) {
        ans.push_back(d * p);
        if (d % p != 0) ans.push_back(d);
    }
    return ans;
}

int get_mobius(int n) {
    int hehe = n;
    if (n == 1) return 1;
    int ans = 1;
    while (n > 1) {
        int p = spf[n];
        n /= p;
        if (n % p == 0) return 0;
        ans *= -1;
    }
    return ans;
}

struct Query {
    int first, second, idx;
};

int n, m, k;
vector<int> arr;
vector<pair<int, int>> *adj;
int lefta[50001];
int righta[50001];
bool visited[50001];
int ans[10001];

bool valid(int t, int from = 0, int to = n - 1) {
    return t >= min(from, to) && t <= max(from, to);
}

void djikstra(int from, int to, int save[]) {
    range(_, from, to + 1) visited[_] = false, save[_] = infinity;
    range(_, to, from + 1) visited[_] = false, save[_] = infinity;


    save[from] = 0;
    priority_queue<pair<int, int>> pq;
    pq.emplace(0, from);
    while (!pq.empty()) {
        auto it = pq.top();
        pq.pop();
        int d = -it.first, curr = it.second;
        visited[curr] = true;
        for (auto nb: adj[curr]) {
            if (!valid(nb.first, from, to)) continue;
            if ((to > from) != (nb.first > curr)) continue;
            if (visited[nb.first]) continue;
            int new_dist = save[curr] + nb.second;
            if (new_dist < save[nb.first]) {
                save[nb.first] = new_dist;
                pq.emplace(-new_dist, nb.first);
            }
        }
    }
}

void dac(int l, int r, vector<Query> queries) {
    if (l == r) return;
    int mid = (l + r) / 2;

    range(t, mid - 10, mid + 10) {
        if (!valid(t, l, r)) continue;

        djikstra(t, l, lefta);
        djikstra(t, r, righta);

        for (auto query: queries) {
            if (query.first > t || query.second < t) continue;
            if (lefta[query.first] == infinity || righta[query.second] == infinity) continue;
            ans[query.idx] = min(ans[query.idx], lefta[query.first] + righta[query.second]);
        }
    }

    vector<Query> hehe[2];
    for (auto query: queries) {
        if (query.first <= mid && query.second >= mid) continue;
        hehe[query.first > mid].push_back(query);
    }

    dac(l, mid, hehe[0]);
    dac(mid + 1, r, hehe[1]);
}


void solve() {

    range(i, 0, 10001) ans[i] = infinity;

    sher(), n = sher(), m = sher();
    int q = sher();
    adj = new vector<pair<int, int>>[n];

    range(i, 0, m) {
        int a = sher(), b = sher(), t = sher();
//        edge[a][b - a] = t;
        adj[b].emplace_back(a, t);
        adj[a].emplace_back(b, t);
    }

    vector<Query> queries;
    range(i, 0, q) {
        int a = sher(), b = sher();
        if (a > b) swap(a, b);
        queries.push_back({a, b, i});
    }


    dac(0, n - 1, queries);

    range(i, 0, q) {
        if (queries[i].first == queries[i].second) {
            print("0");
            continue;
        }
        int x = ans[i];
        if (x == infinity) print("-1");
        else print(x);
    }


}


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

//    freopen("marathon.in", "r", stdin);
//    freopen("marathon.out", "w", stdout);

//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//#endif


//    sieve(1000001);

    int T = 1;
//    cin >> T;

    while (T--) {
        solve();
    }


    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44