oj.uz

Submission #878977

# Submission time Handle Problem Language Result Execution time Memory
878977 2023-11-25T22:35:52 Z AverageAmogusEnjoyer Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 541 ms 63828 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,1:0; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,1:0; }
const int N=1e5;
vector<pair<int,int>> adj[N];
int dist[N][2];
int travel_plan(int n, int m, int edges[][2], int t[], int k, int exits[]) {
    for (int i=0;i<m;i++) {
        adj[edges[i][0]].emplace_back(edges[i][1],t[i]);
        adj[edges[i][1]].emplace_back(edges[i][0],t[i]);
    }
    set<pair<int,int>> q;
    memset(dist,0x3f,sizeof(dist));
    for (int i=0;i<k;i++) {
        dist[exits[i]][0]=dist[exits[i]][1]=0;
        q.insert(make_pair(0,exits[i]));
    }
    while(!q.empty()) {
        int u=(*q.begin()).second; 
        int d=dist[u][1]; 
        q.erase(q.begin());
        for (auto &[v,len]: adj[u]) {
            assert(dist[v][0]<=dist[v][1]);
            if (d+len<dist[v][0]) {
                q.erase(make_pair(dist[v][1],v));
                dist[v][1]=dist[v][0];
                dist[v][0]=d+len;
                q.insert(make_pair(dist[v][1],v));
            } else if (d+len<dist[v][1]) {
                q.erase(make_pair(dist[v][1],v));
                dist[v][1]=d+len;
                q.insert(make_pair(dist[v][1],v));
            }
        }
    }
    return dist[0][1];
}   
/*
int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    int n,m,k; cin >> n >> m >> k;
    int edges[m][2],t[m],exits[k];
    for (int i=0;i<m;i++) {
        cin >> edges[i][0] >> edges[i][1] >> t[i];
    }
    for (int i=0;i<k;i++) {
        cin >> exits[i];
    }
    int res; cin >> res;
    assert(res==travel_plan(n,m,edges,t,k,exits));
}
*/

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 3 ms 6744 KB Output is correct
5 Correct 2 ms 6608 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6608 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 3 ms 6744 KB Output is correct
5 Correct 2 ms 6608 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6608 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6744 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6864 KB Output is correct
12 Correct 4 ms 7004 KB Output is correct
13 Correct 3 ms 7004 KB Output is correct
14 Correct 2 ms 6596 KB Output is correct
15 Correct 2 ms 6900 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 3 ms 6744 KB Output is correct
5 Correct 2 ms 6608 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6608 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6744 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6864 KB Output is correct
12 Correct 4 ms 7004 KB Output is correct
13 Correct 3 ms 7004 KB Output is correct
14 Correct 2 ms 6596 KB Output is correct
15 Correct 2 ms 6900 KB Output is correct
16 Correct 359 ms 60336 KB Output is correct
17 Correct 58 ms 16552 KB Output is correct
18 Correct 98 ms 18012 KB Output is correct
19 Correct 541 ms 63828 KB Output is correct
20 Correct 205 ms 54200 KB Output is correct
21 Correct 33 ms 10320 KB Output is correct
22 Correct 232 ms 51500 KB Output is correct