답안 #975115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
975115	2024-05-04T13:11:18 Z	8pete8	Security Guard (JOI23_guard)	C++17	37 / 100	282 ms	25272 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<n-1;i++){
		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	1 ms	6492 KB	Output is correct
2	Correct	178 ms	22748 KB	Output is correct
3	Correct	179 ms	21696 KB	Output is correct
4	Correct	172 ms	15936 KB	Output is correct
5	Correct	169 ms	15968 KB	Output is correct
6	Correct	168 ms	15924 KB	Output is correct
7	Correct	169 ms	15804 KB	Output is correct
8	Correct	2 ms	6488 KB	Output is correct

Subtask #2

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	178 ms	22748 KB	Output is correct
3	Correct	179 ms	21696 KB	Output is correct
4	Correct	172 ms	15936 KB	Output is correct
5	Correct	169 ms	15968 KB	Output is correct
6	Correct	168 ms	15924 KB	Output is correct
7	Correct	169 ms	15804 KB	Output is correct
8	Correct	2 ms	6488 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	168 ms	14384 KB	Output is correct
11	Correct	217 ms	22016 KB	Output is correct
12	Correct	195 ms	20804 KB	Output is correct
13	Correct	197 ms	20928 KB	Output is correct
14	Correct	170 ms	14488 KB	Output is correct
15	Correct	170 ms	14376 KB	Output is correct
16	Correct	171 ms	14428 KB	Output is correct
17	Correct	168 ms	14436 KB	Output is correct

Subtask #3

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	178 ms	22748 KB	Output is correct
3	Correct	179 ms	21696 KB	Output is correct
4	Correct	172 ms	15936 KB	Output is correct
5	Correct	169 ms	15968 KB	Output is correct
6	Correct	168 ms	15924 KB	Output is correct
7	Correct	169 ms	15804 KB	Output is correct
8	Correct	2 ms	6488 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	168 ms	14384 KB	Output is correct
11	Correct	217 ms	22016 KB	Output is correct
12	Correct	195 ms	20804 KB	Output is correct
13	Correct	197 ms	20928 KB	Output is correct
14	Correct	170 ms	14488 KB	Output is correct
15	Correct	170 ms	14376 KB	Output is correct
16	Correct	171 ms	14428 KB	Output is correct
17	Correct	168 ms	14436 KB	Output is correct
18	Correct	2 ms	6492 KB	Output is correct
19	Correct	248 ms	15372 KB	Output is correct
20	Correct	215 ms	15316 KB	Output is correct
21	Correct	233 ms	15440 KB	Output is correct
22	Correct	259 ms	16064 KB	Output is correct
23	Correct	240 ms	16660 KB	Output is correct
24	Correct	242 ms	20328 KB	Output is correct
25	Correct	269 ms	22764 KB	Output is correct
26	Correct	255 ms	23048 KB	Output is correct
27	Correct	272 ms	25272 KB	Output is correct
28	Correct	207 ms	15492 KB	Output is correct
29	Correct	235 ms	17084 KB	Output is correct
30	Correct	239 ms	20168 KB	Output is correct
31	Correct	255 ms	23740 KB	Output is correct
32	Correct	282 ms	24524 KB	Output is correct
33	Correct	206 ms	16720 KB	Output is correct
34	Correct	262 ms	22724 KB	Output is correct
35	Correct	270 ms	25076 KB	Output is correct
36	Correct	258 ms	23488 KB	Output is correct
37	Correct	265 ms	24260 KB	Output is correct
38	Correct	233 ms	17856 KB	Output is correct
39	Correct	244 ms	18736 KB	Output is correct
40	Correct	257 ms	19216 KB	Output is correct
41	Correct	230 ms	20672 KB	Output is correct
42	Correct	246 ms	22392 KB	Output is correct
43	Correct	262 ms	16156 KB	Output is correct
44	Correct	260 ms	16468 KB	Output is correct
45	Correct	270 ms	16424 KB	Output is correct
46	Correct	268 ms	16460 KB	Output is correct
47	Correct	260 ms	16228 KB	Output is correct
48	Correct	267 ms	16152 KB	Output is correct
49	Correct	247 ms	17352 KB	Output is correct
50	Correct	238 ms	15748 KB	Output is correct
51	Correct	243 ms	15956 KB	Output is correct
52	Correct	204 ms	16196 KB	Output is correct

Subtask #4

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	178 ms	22748 KB	Output is correct
3	Correct	179 ms	21696 KB	Output is correct
4	Correct	172 ms	15936 KB	Output is correct
5	Correct	169 ms	15968 KB	Output is correct
6	Correct	168 ms	15924 KB	Output is correct
7	Correct	169 ms	15804 KB	Output is correct
8	Correct	2 ms	6488 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	168 ms	14384 KB	Output is correct
11	Correct	217 ms	22016 KB	Output is correct
12	Correct	195 ms	20804 KB	Output is correct
13	Correct	197 ms	20928 KB	Output is correct
14	Correct	170 ms	14488 KB	Output is correct
15	Correct	170 ms	14376 KB	Output is correct
16	Correct	171 ms	14428 KB	Output is correct
17	Correct	168 ms	14436 KB	Output is correct
18	Correct	2 ms	6492 KB	Output is correct
19	Correct	248 ms	15372 KB	Output is correct
20	Correct	215 ms	15316 KB	Output is correct
21	Correct	233 ms	15440 KB	Output is correct
22	Correct	259 ms	16064 KB	Output is correct
23	Correct	240 ms	16660 KB	Output is correct
24	Correct	242 ms	20328 KB	Output is correct
25	Correct	269 ms	22764 KB	Output is correct
26	Correct	255 ms	23048 KB	Output is correct
27	Correct	272 ms	25272 KB	Output is correct
28	Correct	207 ms	15492 KB	Output is correct
29	Correct	235 ms	17084 KB	Output is correct
30	Correct	239 ms	20168 KB	Output is correct
31	Correct	255 ms	23740 KB	Output is correct
32	Correct	282 ms	24524 KB	Output is correct
33	Correct	206 ms	16720 KB	Output is correct
34	Correct	262 ms	22724 KB	Output is correct
35	Correct	270 ms	25076 KB	Output is correct
36	Correct	258 ms	23488 KB	Output is correct
37	Correct	265 ms	24260 KB	Output is correct
38	Correct	233 ms	17856 KB	Output is correct
39	Correct	244 ms	18736 KB	Output is correct
40	Correct	257 ms	19216 KB	Output is correct
41	Correct	230 ms	20672 KB	Output is correct
42	Correct	246 ms	22392 KB	Output is correct
43	Correct	262 ms	16156 KB	Output is correct
44	Correct	260 ms	16468 KB	Output is correct
45	Correct	270 ms	16424 KB	Output is correct
46	Correct	268 ms	16460 KB	Output is correct
47	Correct	260 ms	16228 KB	Output is correct
48	Correct	267 ms	16152 KB	Output is correct
49	Correct	247 ms	17352 KB	Output is correct
50	Correct	238 ms	15748 KB	Output is correct
51	Correct	243 ms	15956 KB	Output is correct
52	Correct	204 ms	16196 KB	Output is correct
53	Correct	1 ms	6492 KB	Output is correct
54	Incorrect	226 ms	15964 KB	Output isn't correct
55	Halted	0 ms	0 KB	-

Subtask #5

0 / 8.0

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

Subtask #6

0 / 18.0

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

Subtask #7

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	178 ms	22748 KB	Output is correct
3	Correct	179 ms	21696 KB	Output is correct
4	Correct	172 ms	15936 KB	Output is correct
5	Correct	169 ms	15968 KB	Output is correct
6	Correct	168 ms	15924 KB	Output is correct
7	Correct	169 ms	15804 KB	Output is correct
8	Correct	2 ms	6488 KB	Output is correct
9	Correct	1 ms	6492 KB	Output is correct
10	Correct	168 ms	14384 KB	Output is correct
11	Correct	217 ms	22016 KB	Output is correct
12	Correct	195 ms	20804 KB	Output is correct
13	Correct	197 ms	20928 KB	Output is correct
14	Correct	170 ms	14488 KB	Output is correct
15	Correct	170 ms	14376 KB	Output is correct
16	Correct	171 ms	14428 KB	Output is correct
17	Correct	168 ms	14436 KB	Output is correct
18	Correct	2 ms	6492 KB	Output is correct
19	Correct	248 ms	15372 KB	Output is correct
20	Correct	215 ms	15316 KB	Output is correct
21	Correct	233 ms	15440 KB	Output is correct
22	Correct	259 ms	16064 KB	Output is correct
23	Correct	240 ms	16660 KB	Output is correct
24	Correct	242 ms	20328 KB	Output is correct
25	Correct	269 ms	22764 KB	Output is correct
26	Correct	255 ms	23048 KB	Output is correct
27	Correct	272 ms	25272 KB	Output is correct
28	Correct	207 ms	15492 KB	Output is correct
29	Correct	235 ms	17084 KB	Output is correct
30	Correct	239 ms	20168 KB	Output is correct
31	Correct	255 ms	23740 KB	Output is correct
32	Correct	282 ms	24524 KB	Output is correct
33	Correct	206 ms	16720 KB	Output is correct
34	Correct	262 ms	22724 KB	Output is correct
35	Correct	270 ms	25076 KB	Output is correct
36	Correct	258 ms	23488 KB	Output is correct
37	Correct	265 ms	24260 KB	Output is correct
38	Correct	233 ms	17856 KB	Output is correct
39	Correct	244 ms	18736 KB	Output is correct
40	Correct	257 ms	19216 KB	Output is correct
41	Correct	230 ms	20672 KB	Output is correct
42	Correct	246 ms	22392 KB	Output is correct
43	Correct	262 ms	16156 KB	Output is correct
44	Correct	260 ms	16468 KB	Output is correct
45	Correct	270 ms	16424 KB	Output is correct
46	Correct	268 ms	16460 KB	Output is correct
47	Correct	260 ms	16228 KB	Output is correct
48	Correct	267 ms	16152 KB	Output is correct
49	Correct	247 ms	17352 KB	Output is correct
50	Correct	238 ms	15748 KB	Output is correct
51	Correct	243 ms	15956 KB	Output is correct
52	Correct	204 ms	16196 KB	Output is correct
53	Correct	1 ms	6492 KB	Output is correct
54	Incorrect	226 ms	15964 KB	Output isn't correct
55	Halted	0 ms	0 KB	-