oj.uz

Submission #988770

# Submission time Handle Problem Language Result Execution time Memory
988770 2024-05-26T02:36:28 Z vjudge1 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 272 ms 48488 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
//#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPD(i, n) for (int i = ( n ) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//void setupIO(){
//    #define name "Whisper"
//    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
//    //Phu Trong from Nguyen Tat Thanh High School for gifted student
//    srand(time(NULL));
//    freopen(name".inp", "r", stdin);
//    freopen(name".out", "w", stdout);
//    cout << fixed << setprecision(10);
//}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }

#define MAX_NODE    100005
#define MAX_EDGE    1000005

int numNode, numEdge;
struct Edge{
    int u, v, w;
    Edge(){}
    Edge(int _u, int _v): u(_u), v(_v){}
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w){}

    int other(int x){return (x ^ u ^ v); }
} edge[MAX_EDGE];

vector<int> G[MAX_NODE];
pair<int, int> F[MAX_NODE];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    numNode = N, numEdge = M;
    for (int i = 0; i < numEdge; ++i){
        edge[i].u = R[i][0], edge[i].v = R[i][1], edge[i].w = L[i];
        G[edge[i].u].emplace_back(i);
        G[edge[i].v].emplace_back(i);
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    for (int i = 0; i < numNode; ++i) F[i] = make_pair(INF, INF);

    for (int i = 0; i < K; ++i){
        F[P[i]].first = F[P[i]].second = 0;

        q.emplace(0, P[i]);
    }
    while (q.size()){
        int du, u; tie(du, u) = q.top(); q.pop();
        if (u == 0) return du;
        if (du > F[u].second) continue;
        for (int &i : G[u]){
            int v = edge[i].other(u);
            int current = F[v].second;
            if (F[v].second > du + edge[i].w){
                F[v].second = du + edge[i].w;
                if (F[v].second < F[v].first) swap(F[v].second, F[v].first);
            }
            if (F[v].second < current) q.emplace(F[v].second, v);
        }
    }
    assert(false);
    return 0;
}
//void Whisper(){
//    int R[4][2] = {{0, 1}, {0, 2}, {3, 2}, {2, 4}};
//    int L[4] = {2, 3, 1, 4};
//    int P[3] = {1, 3, 4};
//
//    cout << travel_plan(5, 4, R, L, 3, P);
//}
//
//
//signed main(){
//    setupIO();
//    int Test = 1;
////    cin >> Test;
//    for ( int i = 1 ; i <= Test ; i++ ){
//        Whisper();
//        if (i < Test) cout << '\n';
//    }
//}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 3 ms 8540 KB Output is correct
13 Correct 2 ms 8796 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 2 ms 8648 KB Output is correct
16 Correct 210 ms 45628 KB Output is correct
17 Correct 42 ms 15964 KB Output is correct
18 Correct 46 ms 16724 KB Output is correct
19 Correct 272 ms 48488 KB Output is correct
20 Correct 143 ms 42580 KB Output is correct
21 Correct 21 ms 10064 KB Output is correct
22 Correct 165 ms 36540 KB Output is correct