oj.uz

Submission #796191

# Submission time Handle Problem Language Result Execution time Memory
796191 2023-07-28T07:40:31 Z 박영우(#10072) Security Guard (JOI23_guard) C++17
8 / 100
 4000 ms 4128 KB 
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 301010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<pii> edges;
ll S[MAX];
int vis[MAX];
int p[MAX];
ll ms[MAX];
int find(int a) {
	if (p[a] == a) return a;
	return p[a] = find(p[a]);
}
bool uni(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	p[b] = a;
	ms[a] = min(ms[a], ms[b]);
	return true;
}
ll ans[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, Q;
	cin >> N >> M >> Q;
	int i;
	if (N > 5000) assert(0);
	for (i = 1; i <= N; i++) cin >> S[i];
	edges.resize(M);
	for (i = 0; i < M; i++) cin >> edges[i].first >> edges[i].second;
	int mx = 1;
	ll pl = 0;
	for (i = 1; i <= N; i++) {
		pl -= S[i];
		if (S[mx] < S[i]) mx = i;
	}
	pl += S[mx];
	for (i = 1; i <= N; i++) p[i] = i;
	sort(edges.begin(), edges.end(), [&](pii p1, pii p2) {return S[p1.first] + S[p1.second] < S[p2.first] + S[p2.second]; });
	vector<pii> medge;
	for (auto& [a, b] : edges) if (uni(a, b)) ans[0] += S[a] + S[b], medge.emplace_back(a, b);
	int j, k;
	for (i = 1; i <= Q; i++) {
		if (medge.empty()) {
			ans[i] = ans[i - 1];
			continue;
		}
		int K = medge.size();
		int mv = 0;
		ll mn = 1e18;
		for (j = 0; j < K; j++) {
			ll sum = 0;
			for (k = 1; k <= N; k++) p[k] = k, ms[k] = S[k];
			for (k = 0; k < K; k++) if (k != j) uni(medge[k].first, medge[k].second), sum += S[medge[k].first] + S[medge[k].second];
			vector<ll> ss;
			for (k = 1; k <= N; k++) if (p[k] == k) ss.push_back(ms[k]);
			sort(ss.begin(), ss.end());
			for (k = 1; k < ss.size(); k++) sum += ss[0] + ss[k];
			if (mn > sum) {
				mn = sum;
				mv = j;
			}
		}
		ans[i] = mn;
		medge.erase(medge.begin() + mv);
	}
	for (i = 0; i <= Q; i++) cout << pl + ans[i] << ln;
}

Compilation message

guard.cpp: In function 'int main()':
guard.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for (k = 1; k < ss.size(); k++) sum += ss[0] + ss[k];
      |                ~~^~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 14 ms 4128 KB Output is correct
9 Correct 14 ms 4092 KB Output is correct
10 Correct 13 ms 3820 KB Output is correct
11 Correct 17 ms 4100 KB Output is correct
12 Correct 13 ms 4008 KB Output is correct
13 Correct 15 ms 4020 KB Output is correct
14 Correct 15 ms 4048 KB Output is correct
15 Correct 20 ms 4052 KB Output is correct
16 Correct 13 ms 4052 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 14 ms 4128 KB Output is correct
9 Correct 14 ms 4092 KB Output is correct
10 Correct 13 ms 3820 KB Output is correct
11 Correct 17 ms 4100 KB Output is correct
12 Correct 13 ms 4008 KB Output is correct
13 Correct 15 ms 4020 KB Output is correct
14 Correct 15 ms 4048 KB Output is correct
15 Correct 20 ms 4052 KB Output is correct
16 Correct 13 ms 4052 KB Output is correct
17 Execution timed out 4034 ms 564 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -