oj.uz

Submission #701234

# Submission time Handle Problem Language Result Execution time Memory
701234 2023-02-20T15:22:36 Z tamthegod Zagrade (COI17_zagrade) C++17
100 / 100
 1196 ms 75048 KB 
// Make the best become better
// No room for laziness
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n;
string s;
vector<int> adj[maxN];
int sz[maxN];
int vis[maxN];
int valid[maxN], valid1[maxN];
pair<int, int> f[maxN], dp[maxN];
int a[maxN];
int res = 0;
int cnt[maxN];
void ReadInput()
{
    cin >> n;
    cin >> s;
    s = ' ' + s;
    for(int i=1; i<=n; i++)
        a[i] = (s[i] == '(' ? 1 : -1);
    for(int i=1; i<n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
}
int dfs(int u, int par)
{
    sz[u] = 1;
    for(int v : adj[u])
    {
        if(v == par || vis[v]) continue;
        sz[u] += dfs(v, u);
    }
    return sz[u];
}
int Find_Centroid(int u, int par, int _sz)
{
    for(int v : adj[u])
    {
        if(v == par || vis[v]) continue;
        if(sz[v] > _sz / 2) return Find_Centroid(v, u, _sz);
    }
    return u;
}
void DFS(int u, int par)
{
    f[u].fi = f[par].fi + a[u];
    f[u].se = max(f[u].fi, f[par].se);
    dp[u].fi = f[u].fi;
    dp[u].se = min(dp[par].se, dp[u].fi);
    valid[u] = f[u].fi >= f[par].se;
    valid1[u] = dp[u].fi <= dp[par].se;
    if(valid1[u]) cnt[-dp[u].fi]++;
    if(valid1[u] && !f[u].fi) res++;
    for(int v : adj[u])
    {
        if(vis[v] || v == par) continue;
        DFS(v, u);
    }
}
void del(int u, int par)
{
    if(valid1[u]) cnt[-dp[u].fi]--;
    for(int v : adj[u])
    {
        if(vis[v] || v == par) continue;
        del(v, u);
    }
}
int root;
void upd(int u, int par)
{
    if(valid[u]) res += cnt[f[u].fi - a[root]];
    for(int v : adj[u])
    {
        if(vis[v] || v == par) continue;
        upd(v, u);
    }
}
void add(int u, int par)
{
    if(valid1[u]) cnt[-dp[u].fi]++;
    for(int v : adj[u])
    {
        if(vis[v] || v == par) continue;
        add(v, u);
    }
}
void Decompose(int u)
{
    root = Find_Centroid(u, 0, dfs(u, 0));
    vis[root] = 1;
    f[u] = {0, 0};
    DFS(root, 0);
    for(int v : adj[root])
    {
        if(vis[v]) continue;
        del(v, root);
        upd(v, root);
        add(v, root);
    }
    del(root, 0);
    for(int v : adj[root])
    {
        if(vis[v]) continue;
        Decompose(v);
    }
}
void Solve()
{
    Decompose(1);
    cout << res;
}
int32_t main()
{
    //freopen("sol.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 13 ms 23892 KB Output is correct
3 Correct 14 ms 23892 KB Output is correct
4 Correct 14 ms 23892 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 13 ms 23920 KB Output is correct
7 Correct 13 ms 23892 KB Output is correct
8 Correct 13 ms 23936 KB Output is correct
9 Correct 14 ms 23952 KB Output is correct
10 Correct 14 ms 23892 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 73732 KB Output is correct
2 Correct 440 ms 74388 KB Output is correct
3 Correct 387 ms 73812 KB Output is correct
4 Correct 436 ms 74124 KB Output is correct
5 Correct 399 ms 73820 KB Output is correct
6 Correct 380 ms 73900 KB Output is correct
7 Correct 407 ms 73732 KB Output is correct
8 Correct 382 ms 73860 KB Output is correct
9 Correct 389 ms 73916 KB Output is correct
10 Correct 376 ms 74940 KB Output is correct
11 Correct 390 ms 73748 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 13 ms 23892 KB Output is correct
3 Correct 14 ms 23892 KB Output is correct
4 Correct 14 ms 23892 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 13 ms 23920 KB Output is correct
7 Correct 13 ms 23892 KB Output is correct
8 Correct 13 ms 23936 KB Output is correct
9 Correct 14 ms 23952 KB Output is correct
10 Correct 14 ms 23892 KB Output is correct
11 Correct 388 ms 73732 KB Output is correct
12 Correct 440 ms 74388 KB Output is correct
13 Correct 387 ms 73812 KB Output is correct
14 Correct 436 ms 74124 KB Output is correct
15 Correct 399 ms 73820 KB Output is correct
16 Correct 380 ms 73900 KB Output is correct
17 Correct 407 ms 73732 KB Output is correct
18 Correct 382 ms 73860 KB Output is correct
19 Correct 389 ms 73916 KB Output is correct
20 Correct 376 ms 74940 KB Output is correct
21 Correct 390 ms 73748 KB Output is correct
22 Correct 1096 ms 56864 KB Output is correct
23 Correct 1110 ms 56848 KB Output is correct
24 Correct 1106 ms 56864 KB Output is correct
25 Correct 1196 ms 56884 KB Output is correct
26 Correct 529 ms 62520 KB Output is correct
27 Correct 563 ms 59804 KB Output is correct
28 Correct 564 ms 58704 KB Output is correct
29 Correct 375 ms 75048 KB Output is correct
30 Correct 374 ms 74924 KB Output is correct
31 Correct 99 ms 57892 KB Output is correct
32 Correct 379 ms 73820 KB Output is correct