oj.uz

Submission #892459

# Submission time Handle Problem Language Result Execution time Memory
892459 2023-12-25T11:19:18 Z AgentPengin Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 350 ms 68836 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<int,int>

using namespace std;

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

int n,m,k;
pair<int,int> dist[MAXN];
vector<pair<int,int>> 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;
    	int 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<int, 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<int, 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 1 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 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 1 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 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 2 ms 7000 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 4 ms 7040 KB Output is correct
13 Correct 3 ms 7008 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 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 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 2 ms 7000 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 4 ms 7040 KB Output is correct
13 Correct 3 ms 7008 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 281 ms 62680 KB Output is correct
17 Correct 66 ms 17872 KB Output is correct
18 Correct 77 ms 19152 KB Output is correct
19 Correct 350 ms 68836 KB Output is correct
20 Correct 206 ms 54252 KB Output is correct
21 Correct 31 ms 10876 KB Output is correct
22 Incorrect 223 ms 51960 KB Output isn't correct
23 Halted 0 ms 0 KB -