oj.uz

Submission #892462

# Submission time Handle Problem Language Result Execution time Memory
892462 2023-12-25T11:22:32 Z AgentPengin Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 378 ms 80836 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;
    		int uv = it.se;
    		if (dist[v].fi > du + uv) {
    			if (dist[v].se > dist[v].fi) dist[v].se = dist[v].fi;
    			dist[v].fi = du + uv;
    			pq.push({dist[v].se,v});
    		} 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 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 1 ms 6744 KB Output is correct
8 Correct 2 ms 6744 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 1 ms 6744 KB Output is correct
8 Correct 2 ms 6744 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 2 ms 6776 KB Output is correct
12 Correct 3 ms 9308 KB Output is correct
13 Correct 3 ms 9340 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 1 ms 6744 KB Output is correct
8 Correct 2 ms 6744 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 2 ms 6776 KB Output is correct
12 Correct 3 ms 9308 KB Output is correct
13 Correct 3 ms 9340 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 302 ms 73872 KB Output is correct
17 Correct 66 ms 20680 KB Output is correct
18 Correct 84 ms 22984 KB Output is correct
19 Correct 378 ms 80836 KB Output is correct
20 Correct 196 ms 59992 KB Output is correct
21 Correct 31 ms 15564 KB Output is correct
22 Incorrect 218 ms 55788 KB Output isn't correct
23 Halted 0 ms 0 KB -