oj.uz

Submission #892464

# Submission time Handle Problem Language Result Execution time Memory
892464 2023-12-25T11:24:19 Z AgentPengin Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 367 ms 76260 KB 
/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include "crocodile.h"
#include<bits/stdc++.h>
#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)
#define pii pair<ll,int>

using namespace std;

const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 1e5 + 5;

int n,m,k;
pair<ll,ll> dist[MAXN];
vector<pair<int,ll>> adj[MAXN];
priority_queue<pii,vector<pii>,greater<pii>> pq;

int travel_plan(int N, int M, int R[][2], int W[], int K, int E[]) {
	memset(dist,0x3f,sizeof dist);
	n = N;
	m = M;
	for (int i = 0;i < m;i++) {
		int u = R[i][0],v = R[i][1],l = W[i];
		adj[u].emplace_back(v,l);
		adj[v].emplace_back(u,l);    	
	}
	k = K;
	for (int i = 0;i < k;i++) {
		int u = E[i];
		pq.push(make_pair(0,u));
    	dist[u] = make_pair(0,0);
	}
	while(!pq.empty()) {
    	int u = pq.top().se;
    	ll du = pq.top().fi;
    	pq.pop();
    	if (du != dist[u].se) continue;
    	for (auto it : adj[u]) {
    		int v = it.fi;
    		ll uv = it.se;
    		if (dist[v].fi > du + uv) {
    			if (dist[v].se > dist[v].fi) dist[v].se = dist[v].fi,pq.push({dist[v].se,v});
    			dist[v].fi = du + uv;
    		} else {
    			if (du + uv < dist[v].se) {
    				dist[v].se = du + uv;
    				pq.push({dist[v].se,v});
    			}
    		}
    	}
    }
    return dist[0].se;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:32:30: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment [-Wclass-memaccess]
   32 |  memset(dist,0x3f,sizeof dist);
      |                              ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from crocodile.cpp:7:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6772 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6748 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 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6772 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 3 ms 9048 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 3 ms 9108 KB Output is correct
13 Correct 4 ms 9308 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6772 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 3 ms 9048 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 3 ms 9108 KB Output is correct
13 Correct 4 ms 9308 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 288 ms 70876 KB Output is correct
17 Correct 48 ms 18544 KB Output is correct
18 Correct 71 ms 20852 KB Output is correct
19 Correct 367 ms 76260 KB Output is correct
20 Correct 193 ms 59728 KB Output is correct
21 Correct 26 ms 15008 KB Output is correct
22 Correct 219 ms 55144 KB Output is correct