Submission #113916

#TimeUsernameProblemLanguageResultExecution timeMemory
113916RockyBConstruction of Highway (JOI18_construction)C++17
16 / 100
2043 ms19576 KiB
/// In The Name Of God #include <bits/stdc++.h> #define f first #define s second #define pb push_back #define pp pop_back #define mp make_pair #define sz(x) (int)x.size() #define sqr(x) ((x) * 1ll * (x)) #define all(x) x.begin(), x.end() #define rep(i, l, r) for (int i = (l); i <= (r); i++) #define per(i, l, r) for (int i = (l); i >= (r); i--) #define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0); #define nl '\n' #define ioi exit(0); typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = (int)1e5 + 7; const int inf = (int)1e9 + 7; const int mod = (int)1e9 + 7; const ll linf = (ll)1e18 + 7; const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}; const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1}; using namespace std; int n; int a[N]; pair <int, int> e[N]; vector <int> g[N]; int sz[N], up[N], par[N], len[N], dep[N]; void dfs_sz(int v = 1, int p = 0) { sz[v]++; par[v] = p; dep[v] = dep[p] + 1; for (auto &to : g[v]) { if (to != p) { dfs_sz(to, v); sz[v] += sz[to]; if (sz[to] > sz[g[v][0]]) swap(g[v][0], to); } } } void dfs(int v = 1) { len[up[v]]++; for (auto to : g[v]) { up[to] = (to == g[v][0] ? up[v] : to); dfs(to); } } vector < pair <int, int > > path[N]; void paint_v(vector < pair <int, int> > &x, int L, int c) { reverse(all(x)); int add = L; while (sz(x)) { auto &it = x.back(); if (it.s <= L) { L -= it.s; x.pp(); } else { it.s -= L; break; } } x.pb({c, add}); reverse(all(x)); } void paint(int v, int x) { paint_v(path[up[v]], dep[v] - dep[up[v]] + 1, x); v = par[up[v]]; while (v) { int cut = dep[v] - dep[up[v]] + 1, L = cut; reverse(all(path[up[v]])); while (sz(path[up[v]])) { auto &it = path[up[v]].back(); if (it.s <= cut) { cut -= it.s; path[up[v]].pp(); } else { it.s -= cut; break; } } path[up[v]].pb({x, L}); reverse(all(path[up[v]])); v = par[up[v]]; } } void calc(int v, int u) { vector < pair <int, int> > s; int L = dep[v] - dep[up[v]] + 1, V = v; for (auto it : path[up[v]]) { if (it.s < L) { s.pb(it), L -= it.s; } else { s.pb({it.f, L}); break; } } reverse(all(s)); v = par[up[v]]; while (v) { int need = dep[v] - dep[up[v]] + 1; vector < pair <int, int > > add; for (auto it : path[up[v]]) { if (it.s < need) { add.pb(it); need -= it.s; } else { add.pb({it.f, need}); break; } } reverse(all(add)); for (auto it : add) s.pb(it); v = par[up[v]]; } reverse(all(s)); ll cnt = 0; rep(i, 0, sz(s) - 1) { rep(j, i + 1, sz(s) - 1) { if (s[i].f > s[j].f) cnt += s[i].s * 1ll * s[j].s; } } paint(V, a[u]); if (sz(path[up[u]]) && path[up[u]].back().f == a[u]) { path[up[u]][sz(path[up[u]]) - 1].s++; } else { path[up[u]].pb({a[u], 1}); } cout << cnt << nl; } int main() { #ifdef IOI2018 freopen ("in.txt", "r", stdin); #endif Kazakhstan cin >> n; rep(i, 1, n) cin >> a[i]; rep(i, 2, n) { cin >> e[i].f >> e[i].s; g[e[i].f].pb(e[i].s); } dfs_sz(); up[1] = 1; dfs(); rep(i, 2, n) { calc(e[i].f, e[i].s); } ioi }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...