제출 #1205856

#제출 시각아이디문제언어결과실행 시간메모리
1205856repmannZagrade (COI17_zagrade)C++20
100 / 100
607 ms48496 KiB
#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; }

컴파일 시 표준 에러 (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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...