Submission #1308840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308840		vili	Zagrade (COI17_zagrade)	C++20	100 / 100	560 ms	48072 KiB

zagrade

// Autor: Ozren Vili Paunovic

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<

#define x first
#define y second

using namespace std;

typedef long long ll;

const int MAXN = 300010;

int n;
char s[MAXN];
vector<int> adj[MAXN];
vector<int> vertices;

int sz[MAXN];
bool vis[MAXN];

int fa[MAXN];
int fb[MAXN];

int mna[MAXN];
int mnb[MAXN];

int sum[MAXN];
int centroid;

ll ans = 0;

void dfs_sz(int x, int dad = -1) {
  vertices.push_back(x);
  sz[x] = 1;
  for (int y : adj[x]) {
    if (y == dad) continue;
    if (vis[y]) continue;
    dfs_sz(y, x);
    sz[x] += sz[y];
  }
}

void setup(int x, int dad = -1) {
  mna[x] = min(0, (int)s[x]);
  mnb[x] = min(0, -(int)s[x]);
  sum[x] = s[x];
  if (dad != -1) {
    mna[x] = min(mna[x], mna[dad] + s[x]);
    mnb[x] = min(mnb[x], mnb[dad] - s[x]);
    sum[x] += sum[dad];
  }

  sz[x] = 1;
  for (int y : adj[x]) {
    if (y == dad) continue;
    if (vis[y]) continue;
    setup(y, x);
    sz[x] += sz[y];
  }
}

void update(int x, int v, int dad = -1) {
  if (mna[x] == 0) fa[sum[x]] += v;
  if (mnb[x] == 0) fb[-sum[x]+s[centroid]] += v;
  for (int y : adj[x]) {
    if (y == dad) continue;
    if (vis[y]) continue;
    update(y, v, x);
  }
}

void decompose(int x) {
  vertices.clear();
  dfs_sz(x);
  int tot = sz[x];
  for (int y : vertices) {
    int mx = tot - sz[y];
    for (int z : adj[y]) {
      if (sz[z] < sz[y] && sz[z] > mx)
        mx = sz[z];
    }
    if (mx*2 <= tot)
      x = y;
  }
  centroid = x;
  vis[x] = true;

  setup(x);

  update(x, 1);
  REP(i, tot+1)
    ans += (ll)fa[i] * fb[i];
  update(x, -1);

  for (int y : adj[x]) {
    if (vis[y]) continue;
    update(y, 1);
    REP(i, sz[y]+1)
      ans -= (ll)fa[i] * fb[i];
    update(y, -1);
  }

  for (int y : adj[x]) {
    if (vis[y]) continue;
    decompose(y);
  }
}

int main(void) {
  scanf("%d", &n);
  scanf("%s", s);
  REP(i, n-1) {
    int u, v;
    scanf("%d%d", &u, &v);
    --u; --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  REP(i, n) {
    if (s[i] == '(') s[i] = 1;
    if (s[i] == ')') s[i] = -1;
  }

  decompose(0);
  printf("%lld\n", ans);

  return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
zagrade.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |   scanf("%s", s);
      |   ~~~~~^~~~~~~~~
zagrade.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~

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