답안 #975383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
975383	2024-05-05T04:57:47 Z	8pete8	Security Guard (JOI23_guard)	C++17	37 / 100	322 ms	29136 KB

guard

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib> 
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define int long long
#define double long double
const int mxn=2e5,inf=1e18,minf=-1e18;
int val[mxn+10];
vector<int>adj[mxn+10];
int mark[mxn+10];
int32_t main(){
	int n,m,q;cin>>n>>m>>q;
	if(q)return 0;
	for(int i=1;i<=n;i++)cin>>val[i];
	for(int i=0;i<m;i++){//m not n-1 bruhhh
		int a,b;cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	pair<pii,int> st={{minf,0},-1};
	for(int i=1;i<=n;i++)st=max(st,{{val[i],adj[i].size()},i});
	int ans=0;
	priority_queue<pair<pii,int>,vector<pair<pii,int>>,greater<pair<pii,int>>>pq;
	//greedy cost, if cost equal then we take the node with the least val first(wanna keep the large val as leaf)
	pq.push({{0,0},st.s});
	while(!pq.empty()){
		int cur=pq.top().s,cost=pq.top().f.f;
		pq.pop();
		if(mark[cur])continue;
		mark[cur]=1;
		ans+=cost;
		for(auto i:adj[cur])pq.push({{val[cur],val[i]},i});
	}
	cout<<ans;
	return 0;
}
/*
non tree
we still need to take the max
we still need to have everything connected
 
we can find mst? cost->val of node????
*/

Subtask #1

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6492 KB	Output is correct
2	Correct	178 ms	24080 KB	Output is correct
3	Correct	176 ms	23668 KB	Output is correct
4	Correct	185 ms	18840 KB	Output is correct
5	Correct	172 ms	18860 KB	Output is correct
6	Correct	165 ms	18888 KB	Output is correct
7	Correct	171 ms	18920 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct

Subtask #2

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6492 KB	Output is correct
2	Correct	178 ms	24080 KB	Output is correct
3	Correct	176 ms	23668 KB	Output is correct
4	Correct	185 ms	18840 KB	Output is correct
5	Correct	172 ms	18860 KB	Output is correct
6	Correct	165 ms	18888 KB	Output is correct
7	Correct	171 ms	18920 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	2 ms	6744 KB	Output is correct
10	Correct	170 ms	18776 KB	Output is correct
11	Correct	220 ms	27028 KB	Output is correct
12	Correct	207 ms	25536 KB	Output is correct
13	Correct	208 ms	25800 KB	Output is correct
14	Correct	170 ms	18980 KB	Output is correct
15	Correct	167 ms	18788 KB	Output is correct
16	Correct	164 ms	18888 KB	Output is correct
17	Correct	166 ms	18768 KB	Output is correct

Subtask #3

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6492 KB	Output is correct
2	Correct	178 ms	24080 KB	Output is correct
3	Correct	176 ms	23668 KB	Output is correct
4	Correct	185 ms	18840 KB	Output is correct
5	Correct	172 ms	18860 KB	Output is correct
6	Correct	165 ms	18888 KB	Output is correct
7	Correct	171 ms	18920 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	2 ms	6744 KB	Output is correct
10	Correct	170 ms	18776 KB	Output is correct
11	Correct	220 ms	27028 KB	Output is correct
12	Correct	207 ms	25536 KB	Output is correct
13	Correct	208 ms	25800 KB	Output is correct
14	Correct	170 ms	18980 KB	Output is correct
15	Correct	167 ms	18788 KB	Output is correct
16	Correct	164 ms	18888 KB	Output is correct
17	Correct	166 ms	18768 KB	Output is correct
18	Correct	2 ms	6600 KB	Output is correct
19	Correct	220 ms	19868 KB	Output is correct
20	Correct	210 ms	19796 KB	Output is correct
21	Correct	236 ms	20116 KB	Output is correct
22	Correct	251 ms	20608 KB	Output is correct
23	Correct	233 ms	21168 KB	Output is correct
24	Correct	259 ms	24776 KB	Output is correct
25	Correct	272 ms	27692 KB	Output is correct
26	Correct	282 ms	29084 KB	Output is correct
27	Correct	243 ms	28648 KB	Output is correct
28	Correct	205 ms	19968 KB	Output is correct
29	Correct	205 ms	21488 KB	Output is correct
30	Correct	245 ms	24788 KB	Output is correct
31	Correct	245 ms	29136 KB	Output is correct
32	Correct	273 ms	27960 KB	Output is correct
33	Correct	200 ms	20344 KB	Output is correct
34	Correct	263 ms	27504 KB	Output is correct
35	Correct	269 ms	27548 KB	Output is correct
36	Correct	263 ms	27840 KB	Output is correct
37	Correct	258 ms	27628 KB	Output is correct
38	Correct	233 ms	22344 KB	Output is correct
39	Correct	236 ms	23052 KB	Output is correct
40	Correct	242 ms	24080 KB	Output is correct
41	Correct	322 ms	24768 KB	Output is correct
42	Correct	251 ms	25276 KB	Output is correct
43	Correct	238 ms	20560 KB	Output is correct
44	Correct	263 ms	21028 KB	Output is correct
45	Correct	260 ms	20636 KB	Output is correct
46	Correct	272 ms	21068 KB	Output is correct
47	Correct	291 ms	20556 KB	Output is correct
48	Correct	262 ms	20552 KB	Output is correct
49	Correct	235 ms	21788 KB	Output is correct
50	Correct	254 ms	20048 KB	Output is correct
51	Correct	251 ms	20644 KB	Output is correct
52	Correct	208 ms	19104 KB	Output is correct

Subtask #4

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6492 KB	Output is correct
2	Correct	178 ms	24080 KB	Output is correct
3	Correct	176 ms	23668 KB	Output is correct
4	Correct	185 ms	18840 KB	Output is correct
5	Correct	172 ms	18860 KB	Output is correct
6	Correct	165 ms	18888 KB	Output is correct
7	Correct	171 ms	18920 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	2 ms	6744 KB	Output is correct
10	Correct	170 ms	18776 KB	Output is correct
11	Correct	220 ms	27028 KB	Output is correct
12	Correct	207 ms	25536 KB	Output is correct
13	Correct	208 ms	25800 KB	Output is correct
14	Correct	170 ms	18980 KB	Output is correct
15	Correct	167 ms	18788 KB	Output is correct
16	Correct	164 ms	18888 KB	Output is correct
17	Correct	166 ms	18768 KB	Output is correct
18	Correct	2 ms	6600 KB	Output is correct
19	Correct	220 ms	19868 KB	Output is correct
20	Correct	210 ms	19796 KB	Output is correct
21	Correct	236 ms	20116 KB	Output is correct
22	Correct	251 ms	20608 KB	Output is correct
23	Correct	233 ms	21168 KB	Output is correct
24	Correct	259 ms	24776 KB	Output is correct
25	Correct	272 ms	27692 KB	Output is correct
26	Correct	282 ms	29084 KB	Output is correct
27	Correct	243 ms	28648 KB	Output is correct
28	Correct	205 ms	19968 KB	Output is correct
29	Correct	205 ms	21488 KB	Output is correct
30	Correct	245 ms	24788 KB	Output is correct
31	Correct	245 ms	29136 KB	Output is correct
32	Correct	273 ms	27960 KB	Output is correct
33	Correct	200 ms	20344 KB	Output is correct
34	Correct	263 ms	27504 KB	Output is correct
35	Correct	269 ms	27548 KB	Output is correct
36	Correct	263 ms	27840 KB	Output is correct
37	Correct	258 ms	27628 KB	Output is correct
38	Correct	233 ms	22344 KB	Output is correct
39	Correct	236 ms	23052 KB	Output is correct
40	Correct	242 ms	24080 KB	Output is correct
41	Correct	322 ms	24768 KB	Output is correct
42	Correct	251 ms	25276 KB	Output is correct
43	Correct	238 ms	20560 KB	Output is correct
44	Correct	263 ms	21028 KB	Output is correct
45	Correct	260 ms	20636 KB	Output is correct
46	Correct	272 ms	21068 KB	Output is correct
47	Correct	291 ms	20556 KB	Output is correct
48	Correct	262 ms	20552 KB	Output is correct
49	Correct	235 ms	21788 KB	Output is correct
50	Correct	254 ms	20048 KB	Output is correct
51	Correct	251 ms	20644 KB	Output is correct
52	Correct	208 ms	19104 KB	Output is correct
53	Correct	2 ms	6492 KB	Output is correct
54	Incorrect	248 ms	20752 KB	Output isn't correct
55	Halted	0 ms	0 KB	-

Subtask #5

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6492 KB	Output is correct
2	Incorrect	3 ms	6492 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #6

0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6492 KB	Output is correct
2	Incorrect	3 ms	6492 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	6492 KB	Output is correct
2	Correct	178 ms	24080 KB	Output is correct
3	Correct	176 ms	23668 KB	Output is correct
4	Correct	185 ms	18840 KB	Output is correct
5	Correct	172 ms	18860 KB	Output is correct
6	Correct	165 ms	18888 KB	Output is correct
7	Correct	171 ms	18920 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	2 ms	6744 KB	Output is correct
10	Correct	170 ms	18776 KB	Output is correct
11	Correct	220 ms	27028 KB	Output is correct
12	Correct	207 ms	25536 KB	Output is correct
13	Correct	208 ms	25800 KB	Output is correct
14	Correct	170 ms	18980 KB	Output is correct
15	Correct	167 ms	18788 KB	Output is correct
16	Correct	164 ms	18888 KB	Output is correct
17	Correct	166 ms	18768 KB	Output is correct
18	Correct	2 ms	6600 KB	Output is correct
19	Correct	220 ms	19868 KB	Output is correct
20	Correct	210 ms	19796 KB	Output is correct
21	Correct	236 ms	20116 KB	Output is correct
22	Correct	251 ms	20608 KB	Output is correct
23	Correct	233 ms	21168 KB	Output is correct
24	Correct	259 ms	24776 KB	Output is correct
25	Correct	272 ms	27692 KB	Output is correct
26	Correct	282 ms	29084 KB	Output is correct
27	Correct	243 ms	28648 KB	Output is correct
28	Correct	205 ms	19968 KB	Output is correct
29	Correct	205 ms	21488 KB	Output is correct
30	Correct	245 ms	24788 KB	Output is correct
31	Correct	245 ms	29136 KB	Output is correct
32	Correct	273 ms	27960 KB	Output is correct
33	Correct	200 ms	20344 KB	Output is correct
34	Correct	263 ms	27504 KB	Output is correct
35	Correct	269 ms	27548 KB	Output is correct
36	Correct	263 ms	27840 KB	Output is correct
37	Correct	258 ms	27628 KB	Output is correct
38	Correct	233 ms	22344 KB	Output is correct
39	Correct	236 ms	23052 KB	Output is correct
40	Correct	242 ms	24080 KB	Output is correct
41	Correct	322 ms	24768 KB	Output is correct
42	Correct	251 ms	25276 KB	Output is correct
43	Correct	238 ms	20560 KB	Output is correct
44	Correct	263 ms	21028 KB	Output is correct
45	Correct	260 ms	20636 KB	Output is correct
46	Correct	272 ms	21068 KB	Output is correct
47	Correct	291 ms	20556 KB	Output is correct
48	Correct	262 ms	20552 KB	Output is correct
49	Correct	235 ms	21788 KB	Output is correct
50	Correct	254 ms	20048 KB	Output is correct
51	Correct	251 ms	20644 KB	Output is correct
52	Correct	208 ms	19104 KB	Output is correct
53	Correct	2 ms	6492 KB	Output is correct
54	Incorrect	248 ms	20752 KB	Output isn't correct
55	Halted	0 ms	0 KB	-