oj.uz

답안 #841021

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
841021 2023-09-01T05:16:53 Z jhwest2 봉쇄 시간 (IOI23_closing) C++17
8 / 100
 110 ms 25092 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 202020;

long long dx[MAXN], dy[MAXN];
vector<pair<int, int>> g[MAXN];

void dfs_x(int p, int v) {
	for (auto [w, x] : g[v]) if (p != x) {
		dx[x] = dx[v] + w;
		dfs_x(v, x);
	}
}
void dfs_y(int p, int v) {
	for (auto [w, x] : g[v]) if (p != x) {
		dy[x] = dy[v] + w;
		dfs_y(v, x);
	}
}
int max_score(int N, int X, int Y, long long K,
              vector<int> U, vector<int> V, vector<int> W)
{
	for (int i = 0; i < N - 1; i++) {
		g[U[i]].push_back({W[i], V[i]});
		g[V[i]].push_back({W[i], U[i]});
	}
	dx[X] = 0;
	dy[Y] = 0;
	dfs_x(-1, X);
	dfs_y(-1, Y);
	long long D = dx[Y];
	long long vx = X;
	long long vy = Y;
	long long tx = 0;
	long long ty = 0;
	for (int i = 0; i < N; i++) {
		if (dx[i] + dy[i] == D) {
			if (dx[i] <= dy[i] && tx < dx[i]) {
				vx = i;
				tx = dx[i];
			}
			if (dx[i] > dy[i] && ty < dy[i]) {
				vy = i;
				ty = dy[i];
			}
		}
	}
	// no overlap
	priority_queue<tuple<long long, int, int, int>> pq;
	pq.push({0, X, -1, 0});
	pq.push({0, Y, -1, 1});
	int ans1 = 0;
	long long tk = K;
	while (!pq.empty()) {
		auto [c, v, p, t] = pq.top();
		pq.pop();
		c = -c;
		if (c > K) break;
		K -= c;
		++ans1;
		for (auto [w, x] : g[v]) if (p != x) {
			if ((v == vx && x == vy) || (v == vy && x == vx)) continue;
			if (t == 0)
				pq.push({-dx[x], x, v, 0});
			else
				pq.push({-dy[x], x, v, 1});
		}
	}
	// yes overlap
	K = tk;
	int ans2 = 0;
	for (int i = 0; i < N; i++) {
		if (dx[i] + dy[i] == D) {
			K -= min(dx[i], dy[i]);
			++ans2;
		}
	}
	if (K >= 0) {
		vector<long long> t1;
		vector<pair<long long, long long>> t2;
		for (int i = 0; i < N; i++) {
			if (dx[i] + dy[i] == D) {
				if (dx[i] <= dy[i]) t1.push_back(dy[i] - dx[i]);
				else t1.push_back(dx[i] - dy[i]);
			}
			else {
				if (dx[i] <= dy[i]) {
					if (dx[i] <= dy[i] - dx[i]) {
						t1.push_back(dx[i]);
						t1.push_back(dy[i] - dx[i]);
					}
					else t2.push_back({dx[i], dy[i]});
				}	
				else {
					if (dy[i] <= dx[i] - dy[i]) {
						t1.push_back(dy[i]);
						t1.push_back(dx[i] - dy[i]);
					}
					else t2.push_back({dy[i], dx[i]});					
				}
			}
		}
		sort(t1.begin(), t1.end());
		sort(t2.begin(), t2.end(), [&](auto p, auto q) {
			return p.second < q.second;
		});
		for (int i = 1; i < t1.size(); i++) t1[i] += t1[i - 1];
		int sz = t2.size();
		vector<long long> pre(sz), suf(sz), sum(sz);
		pre[0] = t2[0].second - t2[0].first;
		sum[0] = t2[0].second;
		for (int i = 1; i < sz; i++) {
			pre[i] = max(pre[i - 1], t2[i].second - t2[i].first);
			sum[i] = sum[i - 1] + t2[i].second;
		}
		suf[sz - 1] = t2[sz - 1].first;
		for (int i = sz - 1; i > 0; i--) {
			suf[i - 1] = min(suf[i], t2[i - 1].first);
		}
		int s = upper_bound(t1.begin(), t1.end(), K) - t1.begin();
		if (suf[0] <= K) {
			s = max(s, 1 + (int)(upper_bound(t1.begin(), t1.end(), K - suf[0]) - t1.begin()));
		}
		for (int i = 0; i < sz; i++) {
			if (sum[i] - pre[i] <= K)
				s = max(s, 2 * i + 1 + (int)(upper_bound(t1.begin(), t1.end(), K - sum[i] + pre[i]) - t1.begin()));
			
			if (sum[i] <= K)
				s = max(s, 2 * i + 2 + (int)(upper_bound(t1.begin(), t1.end(), K - sum[i]) - t1.begin()));
			
			if (i != sz - 1 && sum[i] + suf[i + 1] <= K)
				s = max(s, 2 * i + 3 + (int)(upper_bound(t1.begin(), t1.end(), K - sum[i] - suf[i + 1]) - t1.begin()));
		}
		ans1 = max(ans1, ans2 + s);
	}
	for (int i = 0; i < N; i++) {
		g[i].clear();
	}
	return ans1;
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for (int i = 1; i < t1.size(); i++) t1[i] += t1[i - 1];
      |                   ~~^~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 23276 KB Output is correct
2 Correct 94 ms 25092 KB Output is correct
3 Correct 56 ms 8272 KB Output is correct

Subtask #2
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 10068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 10068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 10068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Runtime error 6 ms 10068 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Runtime error 6 ms 10068 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Runtime error 6 ms 10068 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Runtime error 6 ms 10068 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Runtime error 6 ms 10068 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -