oj.uz

Submission #1082066

# Submission time Handle Problem Language Result Execution time Memory
1082066 2024-08-30T16:28:52 Z CELD_07 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 362 ms 93356 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
#define endl "\n"
#define inf 1e15
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
vector<vector<pair<ll, ll>>> adj;
vector<pair<ll, ll>> dist;
vector<bool> visited;
inline void dijkstra(int g[], int k){
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
for(int i=0; i<k; i++)pq.push({0, g[i]}), dist[g[i]]={0, 0};
while(!pq.empty()){
ll o, o1;
tie(o, o1)=pq.top();
pq.pop();
if(visited[o1])continue;
visited[o1]=1;
for(auto& [y, w]: adj[o1]){
if(o+w<dist[y].ft){
dist[y].sd=dist[y].ft;
dist[y].ft=o+w;
pq.push({dist[y].sd, y});
}else if(dist[y].sd>o+w){
dist[y].sd=o+w;
pq.push({dist[y].sd, y});
}
}
}
}
int travel_plan(int N, int M, int R[][2], int W[], int K, int E[]){
ll a, b, c, d, e;
adj.clear();
dist.clear();
visited.clear();
visited.assign(N+1, 0);
adj.resize(N+1);
dist.assign(N+1, {inf, inf});
for(int i=0; i<M; i++){
adj[R[i][0]].push_back({R[i][1], W[i]});
adj[R[i][1]].push_back({R[i][0], W[i]});
}
dijkstra(E, K);
return dist[0].sd;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:42:4: warning: unused variable 'a' [-Wunused-variable]
   42 | ll a, b, c, d, e;
      |    ^
crocodile.cpp:42:7: warning: unused variable 'b' [-Wunused-variable]
   42 | ll a, b, c, d, e;
      |       ^
crocodile.cpp:42:10: warning: unused variable 'c' [-Wunused-variable]
   42 | ll a, b, c, d, e;
      |          ^
crocodile.cpp:42:13: warning: unused variable 'd' [-Wunused-variable]
   42 | ll a, b, c, d, e;
      |             ^
crocodile.cpp:42:16: warning: unused variable 'e' [-Wunused-variable]
   42 | ll a, b, c, d, e;
      |                ^

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 420 KB Output is correct
12 Correct 3 ms 1112 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 420 KB Output is correct
12 Correct 3 ms 1112 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 275 ms 83532 KB Output is correct
17 Correct 60 ms 19908 KB Output is correct
18 Correct 80 ms 22224 KB Output is correct
19 Correct 362 ms 93356 KB Output is correct
20 Correct 177 ms 65272 KB Output is correct
21 Correct 29 ms 8656 KB Output is correct
22 Correct 224 ms 63152 KB Output is correct