oj.uz

Submission #796211

# Submission time Handle Problem Language Result Execution time Memory
796211 2023-07-28T07:59:43 Z 박상훈(#10069) Security Guard (JOI23_guard) C++17
8 / 100
 4000 ms 39332 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr ll INF2 = 4e18;

ll ans;

vector<int> adj[200200], G[200200];
ll a[200200];
int par[200200], deg[200200];

struct DSU{
	int path[200200], mn[200200];
	void init(int n){for (int i=1;i<=n;i++) path[i] = i, mn[i] = a[i];}
	int find(int s){
		if (s==path[s]) return s;
		return path[s] = find(path[s]);
	}
	int merge(int s, int v){
		s = find(s), v = find(v);
		if (s==v) return 0;

		mn[s] = std::min(mn[s], mn[v]);
		path[v] = s;
		return 1;
	}
	int min(int s){return mn[find(s)];}
}dsu;


void dfs(int s, int pa){
	par[s] = pa;
	ans += a[pa];
	for (auto &v:G[s]) if (v!=pa) dfs(v, s);
}

vector<ll> naive(int n, int q, vector<pair<int, int>> E, ll ofs){
	vector<ll> ret(n, INF2);
	for (int z=0;z<(1<<(n-1));z++){
		dsu.init(n);

		ll val = 0;
		vector<ll> V;

		for (int i=0;i<n-1;i++) if (z&(1<<i)){
			dsu.merge(E[i].first, E[i].second);
			val += a[E[i].first] + a[E[i].second];
		}

		for (int i=1;i<=n;i++) if (dsu.find(i)==i){
			V.push_back(dsu.min(i));
			val += V.back();
		}

		sort(V.begin(), V.end());
		val += V[0] * (int)(V.size()-2);

		ret[(int)V.size()-1] = min(ret[(int)V.size()-1], val + ofs);
	}

	if ((int)ret.size() > q+1) ret.resize(q+1);
	while((int)ret.size() < q+1) ret.push_back(ret.back());

	return ret;
}

int main(){
	int n, m, q;
	scanf("%d %d %d", &n, &m, &q);

	for (int i=1;i<=n;i++) scanf("%lld", a+i);
	int root = max_element(a+1, a+n+1) - a;
	
	for (int i=1;i<=m;i++){
		int x, y;
		scanf("%d %d", &x, &y);
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	vector<array<ll, 3>> E;

	dsu.init(n);

	for (int i=1;i<=n;i++){
		for (auto &v:adj[i]) if (dsu.find(i) != dsu.find(v)){
			E.push_back({a[i] + a[v], i, v});
		}
	}

	sort(E.begin(), E.end());

	vector<pair<int, int>> Edge;
	for (auto &[z, x, y]:E) if (dsu.merge(x, y)){
		G[x].push_back(y);
		G[y].push_back(x);

		Edge.emplace_back(x, y);
	}

	ans = a[root];
	for (int i=1;i<=n;i++) ans -= a[i];

	auto rans = naive(n, q, Edge, ans);
	for (auto &x:rans) printf("%lld\n", x);

	// for (auto &[v, w]:Edge) ans += a[v] + a[w];

	// printf("%lld\n", ans);
}

Compilation message

guard.cpp: In function 'int main()':
guard.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
guard.cpp:73:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  for (int i=1;i<=n;i++) scanf("%lld", a+i);
      |                         ~~~~~^~~~~~~~~~~~~
guard.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 110 ms 39332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 110 ms 39332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 110 ms 39332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 110 ms 39332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9716 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 31 ms 13584 KB Output is correct
9 Correct 32 ms 13536 KB Output is correct
10 Correct 31 ms 13384 KB Output is correct
11 Correct 32 ms 13576 KB Output is correct
12 Correct 32 ms 13556 KB Output is correct
13 Correct 35 ms 13500 KB Output is correct
14 Correct 32 ms 13540 KB Output is correct
15 Correct 34 ms 13628 KB Output is correct
16 Correct 36 ms 13556 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9716 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 31 ms 13584 KB Output is correct
9 Correct 32 ms 13536 KB Output is correct
10 Correct 31 ms 13384 KB Output is correct
11 Correct 32 ms 13576 KB Output is correct
12 Correct 32 ms 13556 KB Output is correct
13 Correct 35 ms 13500 KB Output is correct
14 Correct 32 ms 13540 KB Output is correct
15 Correct 34 ms 13628 KB Output is correct
16 Correct 36 ms 13556 KB Output is correct
17 Execution timed out 4067 ms 11724 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 110 ms 39332 KB Output isn't correct
3 Halted 0 ms 0 KB -