제출 #672787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
672787		vjudge1	The Xana coup (BOI21_xanadu)	C++11	10 / 100	90 ms	25988 KiB

xanadu

/*#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")*/
#include <bits/stdc++.h>
#include <set>
#include <map>
using namespace std;
#define ll long long
#define N (ll)((ll)1e5+5)
#define M ((ll)998244353)
#define fi first
#define se second
ll n, dp[N][2][2], k;
bool on[N];
vector<ll> v[N];
void dfs(ll s, ll par) {
	if (v[s].size() == 1 && s != 1) {dp[s][1][0] = 1e6; dp[s][1][1] = 1; dp[s][0][0] = 0; dp[s][0][1] = 1e6;return;}
	vector<pair<ll, ll>> p[2]; for (auto x : v[s]) if (x != par) {
		dfs(x, s); 
		p[0].push_back({ dp[x][on[x]][1] - dp[x][on[x]][0], dp[x][on[x]][0] });
		p[1].push_back({ dp[x][on[x]^1][1] - dp[x][on[x]^1][0], dp[x][on[x]^1][0] });
	}
	sort(p[0].begin(), p[0].end()); sort(p[1].begin(), p[1].end());
	ll k = 0; for (auto x : p[0]) k += x.second; dp[s][0][0] = k; dp[s][1][0] = k + p[0][0].first;
	for (int i = 1; i < p[0].size(); i++) if (p[0][i].first + p[0][i - 1ll].fi <= 0) dp[s][0][0] += p[0][i].first + p[0][i - 1ll].fi;
	for (int i = 2; i < p[0].size(); i++) if (p[0][i].fi + p[0][i - 1ll].fi <= 0) dp[s][1][0] += p[0][i].fi + p[0][i - 1ll].fi;
	k = 0; for (auto x : p[1]) k += x.second; dp[s][1][1] = k + 1; dp[s][0][1] = k + p[1][0].first + 1;
	for (int i = 1; i < p[1].size(); i++) if (p[1][i].fi + p[1][i - 1ll].fi <= 0) dp[s][1][1] += p[1][i].fi + p[1][i - 1ll].fi;
	for (int i = 2; i < p[1].size(); i++) if (p[1][i].fi + p[1][i - 1ll].fi <= 0) dp[s][0][1] += p[1][i].fi + p[1][i - 1ll].fi;
}
int32_t main() {
#define int ll
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	ll a, b; cin >> n; for (int i = 1; i < n; i++) cin >> a >> b, v[a].push_back(b), v[b].push_back(a); for (int i = 1; i <= n; i++) cin >> on[i];
	dfs(1, 0); if (min(dp[1][on[1]][0], dp[1][on[1]][1]) > n) cout << "impossible";
	else cout << min(dp[1][on[1]][0], dp[1][on[1]][1]);
}

컴파일 시 표준 에러 (stderr) 메시지

xanadu.cpp: In function 'void dfs(long long int, long long int)':
xanadu.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int i = 1; i < p[0].size(); i++) if (p[0][i].first + p[0][i - 1ll].fi <= 0) dp[s][0][0] += p[0][i].first + p[0][i - 1ll].fi;
      |                  ~~^~~~~~~~~~~~~
xanadu.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (int i = 2; i < p[0].size(); i++) if (p[0][i].fi + p[0][i - 1ll].fi <= 0) dp[s][1][0] += p[0][i].fi + p[0][i - 1ll].fi;
      |                  ~~^~~~~~~~~~~~~
xanadu.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for (int i = 1; i < p[1].size(); i++) if (p[1][i].fi + p[1][i - 1ll].fi <= 0) dp[s][1][1] += p[1][i].fi + p[1][i - 1ll].fi;
      |                  ~~^~~~~~~~~~~~~
xanadu.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for (int i = 2; i < p[1].size(); i++) if (p[1][i].fi + p[1][i - 1ll].fi <= 0) dp[s][0][1] += p[1][i].fi + p[1][i - 1ll].fi;
      |                  ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 10 / 10
• Subtask 4: 0 / 40
• Subtask 5: 0 / 30