Submission #931663

#	Time	Username	Problem	Language	Result	Execution time	Memory
931663		vjudge1	Zagrade (COI17_zagrade)	C++17	10 / 100	192 ms	1480 KiB

zagrade

#include <bits/stdc++.h>
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define fast_io ios::sync_with_stdio(false);cin.tie(0);
#define what(x) cerr << #x << " is " << x << '\n';
#define kill(x) {cout << x << endl; return 0;}
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define pb push_back
#define ll long long
#define F first
#define S second
const ll inf = 1e18, mod = 1e9 + 7, delta = 1e9 + 9, SQ = 450, P = 6065621;
 
using namespace std;

const int N = 1010, LG = 13;
int n, m, h[N], par[N][LG];
vector<int> adj[N];
string s, t;

bool check (string s) {
  int n = s.size();
  int cnt = 0;
  for (auto u: s) {
    if (u == '(') ++cnt;
    else {
      if (cnt == 0) return false;
      --cnt;
    }
  }
  return cnt == 0;
}

void dfs (int v, int p = -1) {
  par[v][0] = p;
  if (p + 1) h[v] = h[p] + 1;
  for (int i = 1; i < LG; i++)
    if (par[v][i - 1] + 1)
      par[v][i] = par[par[v][i - 1]][i - 1];
  for (auto u: adj[v])
    if (u - p) dfs(u, v);
}

int lca (int u, int v) {
  if (h[u] < h[v]) swap(u, v);
  for (int i = LG - 1; i >= 0; i--) 
    if (par[u][i] + 1 && h[par[u][i]] >= h[v])
      u = par[u][i];
  if (u == v) return v;
  for (int i = LG - 1; i >= 0; i--)
    if (par[u][i] != par[v][i])
      u = par[u][i], v = par[v][i];
  return par[v][0];
}

int main () {
  fast_io;
  cin >> n >> t;
  t = '.' + t;
  memset(par, -1, sizeof par);
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].pb(v);
    adj[v].pb(u);
  }
  dfs(1);
  int ans = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (i == j) continue;
      s = "";
      int l = lca(i, j);
      if (l == i) {
        for (int f = j; f != i; f = par[f][0])
          s += t[f];
        s += t[i];
        reverse(all(s));
        if (check(s)) ++ans;
        // cout << "fuck " << i << ' ' << j << ' ' << s << endl;
      }
      else if (l == j) {
        for (int f = i; f != j; f = par[f][0])
          s += t[f];
        s += t[j];
        if (check(s)) ++ans;
        // cout << "fuck " << i << ' ' << j << ' ' << s << endl;
      }
      else {
        string aa = "";
        string bb = "";
        for (int f = i; f != l; f = par[f][0])
          aa += t[f];
        aa += t[l];
        for (int f = j; f != l; f = par[f][0])
          bb += t[f];
        reverse(all(bb));
        aa += bb;
        s = aa;
        if (check(aa)) ++ans;
        // cout << "fuck " << i << ' ' << j << ' ' << s << endl;
      }
    }
  cout << ans << '\n';
  return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'bool check(std::string)':
zagrade.cpp:22:7: warning: unused variable 'n' [-Wunused-variable]
   22 |   int n = s.size();
      |       ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60