oj.uz

Submission #796221

# Submission time Handle Problem Language Result Execution time Memory
796221 2023-07-28T08:07:19 Z 박영우(#10072) Security Guard (JOI23_guard) C++17
8 / 100
 4000 ms 14804 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];
vector<int> adj[MAX];
int minv = 1;
int mins[MAX];
pll upv;
int prt[MAX];
void dfs(int x, int p = 0) {
	prt[x] = p;
	mins[x] = x;
	for (auto v : adj[x]) {
		if (v == p) continue;
		dfs(v, x);
		if (S[mins[x]] > S[mins[v]]) mins[x] = mins[v];
	}
	if (p) upv = min(upv, pll(-S[p] - S[x] + S[mins[x]] + S[minv], x));
}
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 <= N; i++) if (S[minv] > S[i]) minv = i;
	for (auto& [a, b] : medge) adj[a].push_back(b), adj[b].push_back(a);
	int ptr = 0;
	for (i = 1; i <= Q; i++) {
		for (j = 1; j <= N; j++) adj[j].clear();
		for (auto& [a, b] : medge) adj[a].push_back(b), adj[b].push_back(a);
		upv = pll(1e18, 0);
		dfs(minv);
		int v = upv.second;
		for (auto& [a, b] : medge) {
			int c = 0;
			if (pii(a, b) == pii(v, prt[v])) c = 1;
			if (pii(b, a) == pii(v, prt[v])) c = 1;
			if (c) {
				a = mins[v];
				b = minv;
			}
			ans[i] += S[a] + S[b];
		}
	}
	for (i = 0; i <= Q; i++) cout << pl + ans[i] << ln;
}

Compilation message

guard.cpp: In function 'int main()':
guard.cpp:70:9: warning: unused variable 'k' [-Wunused-variable]
   70 |  int j, k;
      |         ^
guard.cpp:73:6: warning: unused variable 'ptr' [-Wunused-variable]
   73 |  int ptr = 0;
      |      ^~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Runtime error 12 ms 14804 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 4 ms 7380 KB Output is correct
2 Runtime error 12 ms 14804 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 4 ms 7380 KB Output is correct
2 Runtime error 12 ms 14804 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 4 ms 7380 KB Output is correct
2 Runtime error 12 ms 14804 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 3 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 4 ms 7496 KB Output is correct
4 Correct 3 ms 7408 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 51 ms 11128 KB Output is correct
9 Correct 65 ms 11188 KB Output is correct
10 Correct 50 ms 10900 KB Output is correct
11 Correct 50 ms 11084 KB Output is correct
12 Correct 50 ms 11084 KB Output is correct
13 Correct 62 ms 11068 KB Output is correct
14 Correct 66 ms 11152 KB Output is correct
15 Correct 51 ms 11192 KB Output is correct
16 Correct 51 ms 11172 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 4 ms 7496 KB Output is correct
4 Correct 3 ms 7408 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 51 ms 11128 KB Output is correct
9 Correct 65 ms 11188 KB Output is correct
10 Correct 50 ms 10900 KB Output is correct
11 Correct 50 ms 11084 KB Output is correct
12 Correct 50 ms 11084 KB Output is correct
13 Correct 62 ms 11068 KB Output is correct
14 Correct 66 ms 11152 KB Output is correct
15 Correct 51 ms 11192 KB Output is correct
16 Correct 51 ms 11172 KB Output is correct
17 Execution timed out 4019 ms 9028 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

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