oj.uz

Submission #472631

# Submission time Handle Problem Language Result Execution time Memory
472631 2021-09-13T23:04:58 Z hidden1 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 703 ms 63512 KB 
#include "crocodile.h"

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define debug(...) cout << "Line: " << __LINE__ << endl; \
    printDebug(", "#__VA_ARGS__, __VA_ARGS__)
template <typename T>
void printDebug(const char* name, T&& arg1) { cout << (name + 2) << " = " << arg1 << endl; }
template <typename T, typename... T2>
void printDebug(const char* names, T&& arg1, T2&&... args) {
    const char* end = strchr(names + 1, ',');
    cout.write(names + 2, end - names - 2) << " = " << arg1 << endl;
    printDebug(end, args...);
}

const int MAX_N = 1e5 + 10;
vector<pair<int, int> > g[MAX_N];
int n, m;
bool starting[MAX_N];
int cnt[MAX_N];
vector<int> dist[MAX_N];

bool push(int x, int val) {
    vector<int> cpy = dist[x];
    dist[x].push_back(val);
    sort(dist[x].begin(), dist[x].end());
    dist[x].resize(2);
    return dist[x] != cpy;
}

int dij() {
    priority_queue<pair<int, int> > pq;
    for(int i = 0; i < n; i ++) {
        dist[i] = {mod, mod};
        if(starting[i]) {
            dist[i] = {0, 0};
            pq.push({0, i});
            pq.push({0, i});
            cnt[i] = 0;
        }
    }
    while(!pq.empty()) {
        auto curr = pq.top(); pq.pop();
        cnt[curr.second] ++;
        if(cnt[curr.second] != 2) {
            continue;
        }
        if(curr.second == 0) {
            return -curr.first;
        }
        for(auto it : g[curr.second]) {
            if(push(it.first, -curr.first  + it.second)) {
                pq.push({curr.first - it.second, it.first});
            }
        }
    }
    return -1;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    n = N;
    for(int i = 0; i < M; i ++) {
        int a = R[i][0], b = R[i][1], c = L[i];
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    for(int i = 0; i < K; i ++) {
        starting[P[i]] = true;
    }
    return dij();
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5144 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5144 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 4 ms 5144 KB Output is correct
12 Correct 8 ms 5452 KB Output is correct
13 Correct 8 ms 5452 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5144 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 4 ms 5144 KB Output is correct
12 Correct 8 ms 5452 KB Output is correct
13 Correct 8 ms 5452 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 703 ms 60452 KB Output is correct
17 Correct 114 ms 18756 KB Output is correct
18 Correct 122 ms 20052 KB Output is correct
19 Correct 638 ms 63512 KB Output is correct
20 Correct 410 ms 51984 KB Output is correct
21 Correct 55 ms 10820 KB Output is correct
22 Correct 426 ms 49256 KB Output is correct