結果
| 問題 | No.2654 [Cherry 6th Tune] Re: start! (Black Sheep) |
| ユーザー |
👑  AngrySadEight
|
| 提出日時 | 2024-01-05 21:18:18 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 892 ms / 7,000 ms |
| コード長 | 6,718 bytes |
| コンパイル時間 | 20,512 ms |
| コンパイル使用メモリ | 271,328 KB |
| 最終ジャッジ日時 | 2025-02-18 16:19:21 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 40 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <algorithm>#include <atcoder/all>#include <bitset>#include <cassert>#include <cmath>#include <ctime>#include <functional>#include <iomanip>#include <iostream>#include <map>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <tuple>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>using namespace std;using namespace atcoder;typedef long long ll;#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define repr(i, n) for (int i = (int)(n)-1; i >= 0; i--)#define repk(i, k, n) for (int i = k; i < (int)(n); i++)#define all(v) v.begin(), v.end()#define mod1 1000000007#define mod2 998244353#define mod3 100000007#define vi vector<int>#define vs vector<string>#define vc vector<char>#define vl vector<ll>#define vb vector<bool>#define vvi vector<vector<int>>#define vvc vector<vector<char>>#define vvl vector<vector<ll>>#define vvb vector<vector<bool>>#define vvvi vector<vector<vector<int>>>#define vvvl vector<vector<vector<ll>>>#define pii pair<int, int>#define pil pair<int, ll>#define pli pair<ll, int>#define pll pair<ll, ll>#define vpii vector<pair<int, int>>#define vpll vector<pair<ll, ll>>#define vvpii vector<vector<pair<int, int>>>#define vvpll vector<vector<pair<ll, ll>>>using mint = modint998244353;template <typename T>void debug(T e) {cerr << e << endl;}template <typename T>void debug(vector<T> &v) {rep(i, v.size()) { cerr << v[i] << " "; }cerr << endl;}template <typename T>void debug(vector<vector<T>> &v) {rep(i, v.size()) {rep(j, v[i].size()) { cerr << v[i][j] << " "; }cerr << endl;}}template <typename T>void debug(vector<pair<T, T>> &v) {rep(i, v.size()) { cerr << v[i].first << " " << v[i].second << endl; }}template <typename T>void debug(set<T> &st) {for (auto itr = st.begin(); itr != st.end(); itr++) {cerr << *itr << " ";}cerr << endl;}template <typename T>void debug(multiset<T> &ms) {for (auto itr = ms.begin(); itr != ms.end(); itr++) {cerr << *itr << " ";}cerr << endl;}template <typename T>void debug(map<T, T> &mp) {for (auto itr = mp.begin(); itr != mp.end(); itr++) {cerr << itr->first << " " << itr->second << endl;}}void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {cerr << H << " ";debug_out(T...);}ll my_pow(ll x, ll n, ll mod) {// 繰り返し二乗法．x^nをmodで割った余り．ll ret;if (n == 0) {ret = 1;} else if (n % 2 == 1) {ret = (x * my_pow((x * x) % mod, n / 2, mod)) % mod;} else {ret = my_pow((x * x) % mod, n / 2, mod);}return ret;}ll inv(ll x, ll mod) { return my_pow(x, mod - 2, mod); }struct BMS {// 2 個の multiset を用いて中央値を取得する機構multiset<ll> ms1;multiset<ll> ms2;ll sum1 = 0;ll sum2 = 0;void balance() {if (ms1.size() < ms2.size()) {auto itr = ms2.begin();ms2.erase(itr);sum2 -= *itr;ms1.insert(*itr);sum1 += *itr;}if (ms1.size() >= ms2.size() + 2) {auto itr = ms1.end();itr--;ms1.erase(itr);sum1 -= *itr;ms2.insert(*itr);sum2 += *itr;}}void insert(ll v) {if (ms1.size() == 0){ms1.insert(v);sum1 += v;}else if (v <= *(ms1.rbegin())) {ms1.insert(v);sum1 += v;} else {ms2.insert(v);sum2 += v;}balance();}void erase(ll v) {// 「ひとつだけ」削除するif (ms1.find(v) != ms1.end()) {ms1.erase(ms1.find(v));sum1 -= v;} else if (ms2.find(v) != ms2.end()) {ms2.erase(ms2.find(v));sum2 -= v;} else {return;}balance();}ll get_size() {ll siz1 = ms1.size();ll siz2 = ms2.size();return siz1 + siz2;}ll get_mean() {ll ret;if (ms1.size() > ms2.size()) {ret = *(ms1.rbegin());} else {ll ms1max = *(ms1.rbegin());ll ms2min = *(ms2.begin());ret = (ms1max + ms2min) / 2;}return ret;}ll get_score() {ll mean = get_mean();ll len_1 = ms1.size();ll len_2 = ms2.size();ll score = (mean * len_1 - sum1) + (sum2 - mean * len_2);return score;}ll get_min_val() { return *(ms1.begin()); }ll get_max_val() { return *(ms2.rbegin()); }};ll INF = 1000000000000000002;void dfs(vector<vector<ll>> &graph, vector<bool> &isvisited, vector<ll> &ans,BMS &bms, vector<ll> &A, ll v) {isvisited[v] = true;bms.insert(A[v]);// この状態で問題を解くif (bms.get_size() <= 2) {ans[v] = -1;} else {ll anssub = INF;ll min_val = bms.get_min_val();bms.erase(min_val);ll min_mean = bms.get_mean();if (min_mean != min_val) {ll min_score = bms.get_score();anssub = min(anssub, min_score);}bms.insert(min_val);ll max_val = bms.get_max_val();bms.erase(max_val);ll max_mean = bms.get_mean();if (max_mean != max_val) {ll max_score = bms.get_score();anssub = min(anssub, max_score);}bms.insert(max_val);if (min_val == max_val) {anssub = 1;}ans[v] = anssub;}for (ll i = 0; i < graph[v].size(); i++) {ll x = graph[v][i];if (isvisited[x]) {continue;}dfs(graph, isvisited, ans, bms, A, graph[v][i]);}bms.erase(A[v]);}int main() {ll N;cin >> N;vector<ll> A(N + 1);for (ll i = 0; i < N + 1; i++) {cin >> A[i];}vector<ll> u(N);vector<ll> v(N);for (ll i = 0; i < N; i++) {cin >> u[i] >> v[i];}vector<vector<ll>> graph(N + 1, vector<ll>(0));for (ll i = 0; i < N; i++) {graph[u[i]].push_back(v[i]);graph[v[i]].push_back(u[i]);}BMS bms;vector<ll> ans(N + 1, -1);vector<bool> isvisited(N + 1, false);dfs(graph, isvisited, ans, bms, A, 0);for (ll i = 1; i <= N; i++) {cout << ans[i] << endl;}}