oj.uz

Submission #988769

# Submission time Handle Problem Language Result Execution time Memory
988769 2024-05-26T02:35:41 Z Whisper Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 238 ms 64544 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 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 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 2 ms 8536 KB Output is correct
7 Correct 2 ms 8696 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 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 2 ms 8536 KB Output is correct
7 Correct 2 ms 8696 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 3 ms 8796 KB Output is correct
13 Correct 3 ms 8916 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 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 2 ms 8536 KB Output is correct
7 Correct 2 ms 8696 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 3 ms 8796 KB Output is correct
13 Correct 3 ms 8916 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 225 ms 61644 KB Output is correct
17 Correct 41 ms 19284 KB Output is correct
18 Correct 48 ms 20056 KB Output is correct
19 Correct 238 ms 64544 KB Output is correct
20 Correct 147 ms 55648 KB Output is correct
21 Correct 23 ms 11576 KB Output is correct
22 Correct 175 ms 50888 KB Output is correct