oj.uz

Submission #866727

# Submission time Handle Problem Language Result Execution time Memory
866727 2023-10-26T22:21:55 Z smirichto Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 997 ms 135720 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pi pair<ll,ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define alll(x) ((x).begin()+1), (x).end()
#define clean(v) (v).resize(distance((v).begin(), unique(all(v))));
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
#define mod mod
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;

void io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

template<class T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

template<class T>
bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }

void nop() {
    cout << -1 << endl;
    return;
}


const int N = 1e5+5 ;
int n , m , vis[N] ;
vector<pi> adj[N] ;
multiset<int> neigh[N] ;
int solve() {

    priority_queue<array<int,2> , vector<array<int,2>> , greater<>> pq ;
    vector<int> dist(n , 2e9) ;
    for(int i = 0 ; i<n ; i++){
        for(auto p : adj[i]){
            if(vis[p.F]) neigh[i].insert(p.S) ;
        }
        if(neigh[i].size()>1){
            int val = *next(neigh[i].begin()) ;
            pq.push({val , i}) ;
            dist[i] = val ;
        }
    }
    while(!pq.empty()){
        auto vec = pq.top() ; pq.pop() ;
        int node = vec[1] , d = vec[0] ;
        if(d!=dist[node] || vis[node]) continue;
        vis[node] = 1 ;
        for(auto p : adj[node]){
            int to = p.F , w = p.S ;
            if(vis[to]) continue;
            neigh[to].insert(d + w) ;
            if(neigh[to].size()>1){
                int val = *next(neigh[to].begin()) ;
                if(ckmin(dist[to] , val)) pq.push({val , to}) ;
            }
        }
    }
    return dist[0] ;
}

ll travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n = N ;
    m = M ;
    for(int i = 0 ; i<m ; i++){
        int u = R[i][0] , v = R[i][1] , w = L[i] ;
        adj[u].pb({v , w}) ;
        adj[v].pb({u , w}) ;
    }
    for(int i = 0 ; i<K ; i++){
        vis[P[i]] = 1 ;
    }
    return solve() ;
}

//int main() {
//#ifndef ONLINE_JUDGE
//    freopen("input.in", "r", stdin);
//    freopen("output.out", "w", stdout);
//#endif
//    io();
//    ll tt = 1;
//    //cin>>tt ;
//    while (tt--) {
//        solve();
//    }
//
//    return 0;
//}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10884 KB Output is correct
9 Correct 4 ms 11352 KB Output is correct
10 Correct 3 ms 11352 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 6 ms 11868 KB Output is correct
13 Correct 5 ms 11904 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 3 ms 10856 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10884 KB Output is correct
9 Correct 4 ms 11352 KB Output is correct
10 Correct 3 ms 11352 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 6 ms 11868 KB Output is correct
13 Correct 5 ms 11904 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 3 ms 10856 KB Output is correct
16 Correct 991 ms 131432 KB Output is correct
17 Correct 64 ms 35672 KB Output is correct
18 Correct 104 ms 37860 KB Output is correct
19 Correct 997 ms 135720 KB Output is correct
20 Correct 342 ms 123236 KB Output is correct
21 Correct 34 ms 22624 KB Output is correct
22 Correct 389 ms 115872 KB Output is correct