Submission #232317

#TimeUsernameProblemLanguageResultExecution timeMemory
232317pedy4000Zagrade (COI17_zagrade)C++14
30 / 100
134 ms37772 KiB
#include <algorithm> #include <iostream> #include <vector> using namespace std; typedef long long ll; const int N = 3e5 + 15, LOG = 20; ll n, ans; string s; int deep[N], up[N], ok[N], OK[N]; bool neg[N]; int ind[N], T; int par[LOG][N]; vector <int> G[N], GP[N]; vector <int> ver[N]; int dp[N], ls[N]; void calc (int v = 0, int p = 0) { par[0][v] = p; for (int i = 1; i < LOG; i++) par[i][v] = par[i - 1][par[i - 1][v]]; ind[T++] = v; deep[v] = 1 + deep[p]; up[v] = up[p] + (s[v] == '('? +1: -1); ok[v] = v; if (s[v] == '(') { int u = ok[p]; if (u != p && u != par[0][u]) u = par[0][u]; if (u != par[0][u] && s[par[0][u]] == '(') u = ok[par[0][u]]; ok[v] = u; } OK[v] = v; if (s[v] == ')') { int u = OK[p]; if (u != p && u != par[0][u]) u = par[0][u]; if (u != par[0][u] && s[par[0][u]] == ')') u = OK[par[0][u]]; OK[v] = u; } for (int u: G[v]) if (u != p) calc(u, v); } int lca (int v, int u) { if (deep[v] < deep[u]) swap(v, u); int dis = deep[v] - deep[u]; for (int i = 0; i < LOG; i++) if ((dis >> i) & 1) v = par[i][v]; if (v == u) return v; for (int i = LOG - 1; ~i; i--) if (par[i][v] != par[i][u]) { v = par[i][v]; u = par[i][u]; } return par[0][v]; } int main() { ios::sync_with_stdio(false), cin.tie(0); cin >> n >> s; for (int i = 0; i < n - 1; i++) { int v, u; cin >> v >> u; v--, u--; G[v].push_back(u); G[u].push_back(v); } if (n <= -1000) { calc(); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { if (i == j) continue; int k = lca(i, j); if (k == i) { if (deep[OK[j]] <= deep[i] && up[j] - up[i] == -((s[i] == '('? +1: -1))) { ans++; } continue; } if (k == j) { if (deep[ok[i]] <= deep[j] && up[i] - up[j] == -((s[j] == '('? +1: -1))) ans++; continue; } if (deep[ok[i]] <= deep[k] && deep[OK[j]] <= deep[k] && up[i] - up[k] + up[j] - up[k] == -((s[k] == '('? +1: -1))) ans++; } cout << ans << "\n"; return 0; } for (int T = 0; T < 2; T++) { for (int i = n - 1; ~i; i--) { ls[i] = -1; dp[i] = 0; if (s[i] == ')') continue; if (i == n - 1) continue; int ind = i + 1; while (ind < n && s[ind] == '(' && ls[ind] != -1) ind = ls[ind] + 1; if (ind == n) continue; if (s[ind] == '(') continue; ls[i] = ind; dp[i] = 1 + dp[ind + 1]; } for (int i = 0; i < n; i++) ans += dp[i]; reverse(s.begin(), s.end()); } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...