제출 #499561

#제출 시각아이디문제언어결과실행 시간메모리
499561bigoTable Tennis (info1cup20_tabletennis)C++14
0 / 100
154 ms7876 KiB
#include <iostream> #include <cmath> #include <math.h> #include <vector> #include <string> #include <algorithm> #include <set> #include <queue> #define M 1000000007 #define pii pair<int, int> typedef long long ll; using namespace std; /* vector<vector<int>>vec; vector<bool>visit; vector<int>w; vector<pair<int, pii>>dp1; vector<pair<int, pii>>dp2; vector<int>pre; pair<int,pii> max1(pair<int, pii>a1, pair<int, pii>a2,bool v1,bool v2) { if (a1.first > a2.first) return a1; else if (a1.first < a2.first) return a2; else { if (v1 and !v2) return a1; if (v2 and !v1) return a2; else { int tmp1 = abs(a1.second.second - a1.second.first); int tmp2 = abs(a2.second.second - a2.second.first); if (tmp1 > tmp2) return a1; else if (tmp2 > tmp1) return a2; else { if (a1.second.second > a2.second.second) { return a1; } else if (a2.second.second > a1.second.second) return a2; else { if (a1.second.first > a2.second.first) { return a2; } else if (a2.second.first > a1.second.first) return a1; else return a1; } } } } } vector<bool>he; void dfs(int v) { visit[v] = true; for (int i = 0; i < vec[v].size(); i++) { if (!visit[vec[v][i]]) { dfs(vec[v][i]); } dp2[v] = max1({ dp1[vec[v][i]].first,{w[v],w[v]} }, dp2[v], true, true); int val2 = abs(w[vec[v][i]] - w[v]) + dp2[vec[v][i]].first; int val = dp1[vec[v][i]].second.second - dp1[vec[v][i]].second.first; int val1 = max(dp1[vec[v][i]].second.second, w[v]) - min(dp1[vec[v][i]].second.first, w[v]); int val3 = dp1[vec[v][i]].first - val + val1; bool tmp123 = he[v]; if (val1 > val) he[v] = true; else he[v] = false; if (val3 >= val2) { pair<int, pii> a1 = max1({ val3,{min(dp1[vec[v][i]].second.first, w[v]),max(dp1[vec[v][i]].second.second, w[v])} }, dp1[v], he[i], tmp123); if (dp1[v] != a1 ) pre[v] = vec[v][i]; dp1[v] = a1; } else { pair <int, pii>a1 = max1({ val2,{min(w[vec[v][i]],w[i]),max(w[vec[v][i]],w[i])} }, dp1[v], he[i], tmp123); if (dp1[v] != a1) pre[v] = vec[v][i]; dp1[v] = a1; } } } vector<int>sed; void bfs(int v) { vector<bool>visit(vec.size()); vector<int>distance1(vec.size()); distance1[v] = 0; for (int i = 0; i < vec.size(); i++) { visit[i] = false; } queue<int>queue1; queue1.push(v); visit[v] = true; while (queue1.empty() == false) { sed.push_back(queue1.front()); int cur = queue1.front(); queue1.pop(); for (int i = 0; i < vec[cur].size(); i++) { if (visit[vec[cur][i]] == false) { visit[vec[cur][i]] = true; distance1[vec[cur][i]] = distance1[cur] + 1; queue1.push(vec[cur][i]); } } } } int main() { ios::sync_with_stdio(false); int n; cin >> n; he.resize(n); pre.resize(n,-1); w.resize(n); for (int i = 0; i < n; i++) cin >> w[i]; vec.resize(n); visit.resize(n, false); vector<int>num(n, 0); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--; v--; vec[u].push_back(v); num[u]++; } dp1.resize(n, { -1,{-1,-1} }); dp2.resize(n, { -1,{-1,-1} }); for (int i = 0; i < n; i++) { if (num[i] == 0) { dp1[i] = { 0,{w[i],w[i]} }; dp2[i] = { 0,{w[i],w[i]} }; visit[i] = true; } } dfs(0); vector<bool>visit1(n, false); ll ans = 0; bfs(0); for (int i = 0; i < n; i++) { if (!visit1[sed[i]]) { ans += dp1[sed[i]].first; int tmp12 = i; while (tmp12!=-1) { visit1[tmp12] = true; tmp12 = pre[tmp12]; } } } cout << ans; }*/ int main() { int n, k; cin >> n >> k; multiset<int>set1; vector<int>vec(n+k); ll sum = 0; for (int i = 0; i < n + k; i++) { cin >> vec[i]; set1.insert(vec[i]); sum += vec[i]; } for (int i = 0; i < n + k; i++) { ll sum1 = sum - vec[i]; set1.erase(set1.find(vec[i])); auto it = set1.begin(); int a1 = *it; ++it; int a2 = *it; int d = a2 - a1; ll sum2 = (2 * a1 + (n - 1) * d) * n / 2; if (sum2 == sum1) { for (int j = 0; j < n + k; j++) { if (j != i) cout << vec[j] << " "; } break; } set1.insert(vec[i]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...