Submission #914823

#TimeUsernameProblemLanguageResultExecution timeMemory
914823vjudge1Papričice (COCI20_papricice)C++17
50 / 110
10 ms604 KiB
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, // __gnu_pbds::tree_order_statistics_node_update > ordered_set; // #include "debugging.h" using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<ll> vll; typedef vector<vi> vvi; typedef vector<vii> vvii; #define pb push_back #define mp make_pair #define all(a) (a).begin(), (a).end() #define f first #define s second #define endl '\n' #define fr(i, x) for (int i = 0; i < x; i++) #define fr1(i, x) for (int i = 1; i <= x; i++) #define FOR(i, x, y) for (ll i = x; i < y; i++) #define lcm(a, b) (a * b) / __gcd(a, b) #define sqr(x) ((x) * (x)) #define cube(x) ((x) * (x) * (x)) #define dbg(v) cerr << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl; #define show(v) cerr << v << " "; #define INT(n) \ int n; \ cin >> n; const int INF = 1e9; const double PI = acos(-1); const int MOD = 1e9 + 7; vvi g(2005, vi()); vector<int> sizes(2005, -1); vector<bool> vis(2005); vi timein(2005), timeout(2005); int dfs(int node, int &time) { if (sizes[node] != -1) return 0; timein[node] = time; time++; sizes[node] = 1; for (auto next : g[node]) { sizes[node] += dfs(next, time); } timeout[node] = time; time++; return sizes[node]; } // is node2 component inside node1 component bool is_in(int node1, int node2) { return timein[node1] < timein[node2] && timeout[node2] < timeout[node1]; } int diff(int a, int b, int c) { return max(abs(a - b), max(abs(b - c), abs(a - c))); } int main() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, a, b; cin >> n; int m = n - 1; fr(i, m) { cin >> a >> b; g[a].pb(b); g[b].pb(a); } int time = 0; dfs(1, time); int comp1, comp2, comp3; int res = 0, final_res = INF; for (int i = 2; i <= n; i++) { for (int j = i + 1; j <= n; j++) { if (is_in(i, j)) { comp1 = sizes[j]; comp2 = sizes[i] - comp1; comp3 = sizes[1] - sizes[i]; } else if (is_in(j, i)) { comp1 = sizes[i]; comp2 = sizes[j] - comp1; comp3 = sizes[1] - sizes[j]; } else { comp1 = sizes[1] - sizes[i] - sizes[j]; comp2 = sizes[j]; comp3 = sizes[i]; } res = diff(comp1, comp2, comp3); final_res = min(final_res, res); } } cout << final_res << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...