Submission #1205856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205856		repmann	Zagrade (COI17_zagrade)	C++20	100 / 100	607 ms	48496 KiB

zagrade

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N;
ll sol;
string S;
int PREF[300096];
int SUFF[300096];
bool V[300096];
int SIZE[300096];
vector <int> VG[300096];
char *pos, BUFFER[5000096];
inline int getnum()
{
   char C;
   while ((C = *pos++) < '0');
   int RET = C -= '0';
   while ((C = *pos++) >= '0') RET = 10 * RET + C - '0';
   return RET;
}
inline void SDFS(int node, queue <pair <int, int>> &Q, int parent = 0)
{
  SIZE[node] = 1;
  Q.push({parent, node});
  for(int x : VG[node])
  {
    if(V[x] || (x == parent)) continue;
    SDFS(x, Q, node);
    SIZE[node] += SIZE[x];
  }
  return;
}
inline int GetCentroid(int node)
{
  int RET = 0, best = INT_MAX, temp;
  queue <pair <int, int>> Q;
  SDFS(node, Q);
  while(Q.size())
  {
    temp = SIZE[node] - SIZE[Q.front().second];
    for(int x : VG[Q.front().second]) if((!V[x]) && (x != Q.front().first)) temp = max(SIZE[x], temp);
    if(temp < best) {RET = Q.front().second; best = temp;}
    Q.pop();
  }
  return RET;
}
inline void DFS1(int node, char c, int &depth, pair <int, int> pref, pair <int, int> suff, int parent = 0)
{
  if(S[node - 1] == '(')
  {
    suff.first++;
    pref.first += !pref.second;
    pref.second -= bool(pref.second);
  }
  else
  {
    pref.second++;
    suff.second += !suff.first;
    suff.first -= bool(suff.first);
  }
  sol += (!suff.first) * PREF[suff.second - (c == ')') + (c == '(')] + (!pref.second) * SUFF[pref.first - (c == '(') + (c == ')')];
  for(int x : VG[node]) if((!V[x]) && (x != parent)) DFS1(x, c, depth, pref, suff, node);
  return;
}
inline void DFS2(int node, char c, int &depth, pair <int, int> pref, pair <int, int> suff, int parent = 0)
{
  if(S[node - 1] == '(')
  {
    suff.first++;
    pref.first += !pref.second;
    pref.second -= bool(pref.second);
  }
  else
  {
    pref.second++;
    suff.second += !suff.first;
    suff.first -= bool(suff.first);
  }
  SUFF[suff.second] += !suff.first;
  PREF[pref.first] += !pref.second;
  depth = max({pref.first, suff.second, depth});
  for(int x : VG[node]) if((!V[x]) && (x != parent)) DFS2(x, c, depth, pref, suff, node);
  return;
}
inline void CD()
{
  int centroid;
  queue <int> Q;
  Q.push(1);
  while(Q.size())
  {
    centroid = GetCentroid(Q.front());
    V[centroid] = true;
    char c = S[centroid - 1];
    PREF[1] = c == '(';
    SUFF[1] = c == ')';
    int depth = 0;
    for(int x : VG[centroid])
    {
      if(V[x]) continue;
      DFS1(x, c, depth, {c == '(', c == ')'}, {c == '(', c == ')'});
      DFS2(x, c, depth, {c == '(', c == ')'}, {c == '(', c == ')'});
      Q.push(x);
    }
    for(; depth + 1; depth--) PREF[depth] = SUFF[depth] = 0;
    Q.pop();
  }
  return;
}
int main()
{
  fread(pos = BUFFER, 1, 5000000, stdin);
  N = getnum();
  while((*pos != '(') && (*pos != ')')) pos++;
  for(int i = 1; i <= N; i++) S.push_back(*pos++);
  int u, v;
  for(int i = 1; i < N; i++)
  {
    u = getnum();
    v = getnum();
    VG[u].push_back(v);
    VG[v].push_back(u);
  }
  CD();
  cout << sol << '\n';

  return 0;
}

Compilation message (stderr)

zagrade.cpp: In function 'int main()':
zagrade.cpp:112:8: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   fread(pos = BUFFER, 1, 5000000, stdin);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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