Submission #701234

#TimeUsernameProblemLanguageResultExecution timeMemory
701234tamthegodZagrade (COI17_zagrade)C++17
100 / 100
1196 ms75048 KiB
// Make the best become better // No room for laziness #include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1e6 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; int n; string s; vector<int> adj[maxN]; int sz[maxN]; int vis[maxN]; int valid[maxN], valid1[maxN]; pair<int, int> f[maxN], dp[maxN]; int a[maxN]; int res = 0; int cnt[maxN]; void ReadInput() { cin >> n; cin >> s; s = ' ' + s; for(int i=1; i<=n; i++) a[i] = (s[i] == '(' ? 1 : -1); for(int i=1; i<n; i++) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } } int dfs(int u, int par) { sz[u] = 1; for(int v : adj[u]) { if(v == par || vis[v]) continue; sz[u] += dfs(v, u); } return sz[u]; } int Find_Centroid(int u, int par, int _sz) { for(int v : adj[u]) { if(v == par || vis[v]) continue; if(sz[v] > _sz / 2) return Find_Centroid(v, u, _sz); } return u; } void DFS(int u, int par) { f[u].fi = f[par].fi + a[u]; f[u].se = max(f[u].fi, f[par].se); dp[u].fi = f[u].fi; dp[u].se = min(dp[par].se, dp[u].fi); valid[u] = f[u].fi >= f[par].se; valid1[u] = dp[u].fi <= dp[par].se; if(valid1[u]) cnt[-dp[u].fi]++; if(valid1[u] && !f[u].fi) res++; for(int v : adj[u]) { if(vis[v] || v == par) continue; DFS(v, u); } } void del(int u, int par) { if(valid1[u]) cnt[-dp[u].fi]--; for(int v : adj[u]) { if(vis[v] || v == par) continue; del(v, u); } } int root; void upd(int u, int par) { if(valid[u]) res += cnt[f[u].fi - a[root]]; for(int v : adj[u]) { if(vis[v] || v == par) continue; upd(v, u); } } void add(int u, int par) { if(valid1[u]) cnt[-dp[u].fi]++; for(int v : adj[u]) { if(vis[v] || v == par) continue; add(v, u); } } void Decompose(int u) { root = Find_Centroid(u, 0, dfs(u, 0)); vis[root] = 1; f[u] = {0, 0}; DFS(root, 0); for(int v : adj[root]) { if(vis[v]) continue; del(v, root); upd(v, root); add(v, root); } del(root, 0); for(int v : adj[root]) { if(vis[v]) continue; Decompose(v); } } void Solve() { Decompose(1); cout << res; } int32_t main() { //freopen("sol.inp", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(nullptr); ReadInput(); Solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...