oj.uz

Submission #783620

# Submission time Handle Problem Language Result Execution time Memory
783620 2023-07-15T06:33:09 Z horiiseun Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 387 ms 63296 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <random>
#include <string>
#include <cassert>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include "crocodile.h"
using namespace std;
 
#define ll long long
#define f first
#define s second
 
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
 
template<typename A> void __print(const A &x);
template<typename A, typename B> void __print(const pair<A, B> &p);
template<typename... A> void __print(const tuple<A...> &t);
template<typename T> void __print(stack<T> s);
template<typename T> void __print(queue<T> q);
template<typename T, typename... U> void __print(priority_queue<T, U...> q);
 
template<typename A> void __print(const A &x) {
    bool first = true;
    cerr << '{';
    for (const auto &i : x) {
        cerr << (first ? "" : ","), __print(i);
        first = false;
    }
    cerr << '}';
}
 
template<typename A, typename B> void __print(const pair<A, B> &p) {
    cerr << '(';
    __print(p.f);
    cerr << ',';
    __print(p.s);
    cerr << ')';
}
 
template<typename... A> void __print(const tuple<A...> &t) {
    bool first = true;
    cerr << '(';
    apply([&first] (const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
    cerr << ')';
}
 
template<typename T> void __print(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    __print(debugVector);
}
 
template<typename T> void __print(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
template<typename T, typename... U> void __print(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
void _print() { cerr << "]\n"; }
 
template <typename Head, typename... Tail> void _print(const Head &H, const Tail &...T) {
    __print(H);
    if (sizeof...(T)) cerr << ", ";
    _print(T...);
}
 
#ifdef DEBUG
	#define D(...) cerr << "Line: " << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
#else
	#define D(...)
#endif

vector<pair<int, int>> adj[100005];
int dist[100005], sdist[100005];
bool seen[100005];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    fill(dist, dist + 100005, 2e9);
    fill(sdist, sdist + 100005, 2e9);
    for (int i = 0; i < M; i++) {
        adj[R[i][0]].push_back({R[i][1], L[i]});
        adj[R[i][1]].push_back({R[i][0], L[i]});
    }
    
    for (int i = 0; i < K; i++) {
        dist[P[i]] = sdist[P[i]] = 0;
        pq.push({0, P[i]});
    }
    while (!pq.empty()) {
        int curr = pq.top().s;
        pq.pop();
        if (seen[curr]) continue;
        seen[curr] = true;
        for (auto [i, d] : adj[curr]) {
            if (sdist[curr] + d < dist[i]) {
                sdist[i] = dist[i];
                dist[i] = sdist[curr] + d;
                pq.push({sdist[i], i});
            } else if (sdist[curr] + d < sdist[i]) {
                sdist[i] = sdist[curr] + d;
                pq.push({sdist[i], i});
            }
        }
    }
    return sdist[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3444 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3540 KB Output is correct
8 Correct 2 ms 3440 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3444 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3540 KB Output is correct
8 Correct 2 ms 3440 KB Output is correct
9 Correct 3 ms 3696 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3540 KB Output is correct
12 Correct 5 ms 3924 KB Output is correct
13 Correct 4 ms 3924 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 2 ms 3540 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3444 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3540 KB Output is correct
8 Correct 2 ms 3440 KB Output is correct
9 Correct 3 ms 3696 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3540 KB Output is correct
12 Correct 5 ms 3924 KB Output is correct
13 Correct 4 ms 3924 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 2 ms 3540 KB Output is correct
16 Correct 305 ms 58808 KB Output is correct
17 Correct 69 ms 14920 KB Output is correct
18 Correct 80 ms 16488 KB Output is correct
19 Correct 387 ms 63296 KB Output is correct
20 Correct 218 ms 50312 KB Output is correct
21 Correct 32 ms 8604 KB Output is correct
22 Correct 235 ms 46812 KB Output is correct