oj.uz

Submission #934792

# Submission time Handle Problem Language Result Execution time Memory
934792 2024-02-28T02:41:48 Z Joshua_Andersson Inside information (BOI21_servers) C++14
80 / 100
 3500 ms 137428 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
//#define int ll
const int inf = int(1e9);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
#define ceildiv(x,y) ((x + y - 1) / (y))

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

#define _LOCAL _DEBUG
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

const int maxn = int(1.5e5);
int tin[maxn];
int tout[maxn];
int timer = 0;
int up[maxn][18];
bool upincreasing[maxn][18];
bool updecreasing[maxn][18];
int upmax[maxn][18];
int upmin[maxn][18];
int upv[maxn];
int depth[maxn];

void dfs(int u, int p, int p1, int _p2, vector<vector<p2>>& edges)
{
    depth[u] = depth[p] + 1;
    tin[u] = timer++;
    up[u][0] = p;
    upmax[u][0] = upv[u];
    upmin[u][0] = upv[u];
    upincreasing[u][0] = upmax[u][0] < upmax[p][0] || p == 0 || u == 0;
    updecreasing[u][0] = upmax[u][0] > upmax[p][0] || p == 0 || u == 0;
    repp(d, 1, 18)
    {
        int mid = up[u][d - 1];
        up[u][d] = up[mid][d - 1];
        upmax[u][d] = max(upmax[u][d - 1], upmax[mid][d - 1]);
        upmin[u][d] = min(upmin[u][d - 1], upmin[mid][d - 1]);
        upincreasing[u][d] = upincreasing[u][d - 1] && upincreasing[mid][d - 1] && (upmax[mid][0] < upmax[up[mid][0]][0] || up[mid][0] == 0 || mid == 0);
        updecreasing[u][d] = updecreasing[u][d - 1] && updecreasing[mid][d - 1] && (upmax[mid][0] > upmax[up[mid][0]][0] || up[mid][0] == 0 || mid == 0);
    }


    repe(e, edges[u]) if (e.first != p)
    {
        upv[e.first] = e.second;
        dfs(e.first, u, p1, _p2, edges);
    }

    tout[u] = timer++;
}

bool isancestor(int a, int b)
{
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int pathmax(int a, int b)
{
    if (isancestor(a, b)) return -1;
    int ret = -1;
    for (int d = 17; d >= 0; d--)
    {
        if (!isancestor(up[a][d], b))
        {
            ret = max(ret, upmax[a][d]);
            a = up[a][d];
        }
    }
    return max(ret, upmax[a][0]);
}

int pathmin(int a, int b)
{
    if (isancestor(a, b)) return inf;
    int ret = inf;
    for (int d = 17; d >= 0; d--)
    {
        if (!isancestor(up[a][d], b))
        {
            ret = min(ret, upmin[a][d]);
            a = up[a][d];
        }
    }
    return min(ret, upmin[a][0]);
}

int lca(int a, int b)
{
    if (isancestor(a, b)) return a;
    if (isancestor(b, a)) return b;
    for (int d = 17; d >= 0; d--)
    {
        if (!isancestor(up[a][d], b))
        {
            a = up[a][d];
        }
    }
    return up[a][0];
}

struct Centroid
{
    int n;
    vvi edges;
    vi vis;
    vi par;
    vi size;

    Centroid() {}
    Centroid(vvi& edges) : edges(edges), n(edges.size()), vis(n), par(n), size(n)
    {
        init_centroid(0, -1);
    }

    int find_centroid(int u, int p, int n)
    {
        repe(e, edges[u])
        {
            if (e == p) continue;
            if (!vis[e] && size[e] > n / 2) return find_centroid(e, u, n);
        }
        return u;
    }

    int find_size(int u, int p)
    {
        if (vis[u]) return 0;
        size[u] = 1;

        repe(e, edges[u])
        {
            if (e == p) continue;
            size[u] += find_size(e, u);
        }
        return size[u];
    }

    void init_centroid(int u, int p)
    {
        find_size(u, u);

        int c = find_centroid(u, u, size[u]);
        vis[c] = 1;
        par[c] = p;

        repe(e, edges[c])
        {
            if (!vis[e]) init_centroid(e, c);
        }
    }
};

int cdepth[maxn];
void d(int u, int p, vvi& adj)
{
    cdepth[u] = cdepth[p] + 1;
    repe(e, adj[u]) if (e != p) d(e, u, adj);
}

signed main()
{
    fast();

    //ifstream in("C:\\Users\\Matis\\desktop\\comp_prog\\x64\\debug\\in.txt");
    //cin.rdbuf(in.rdbuf());

    int n, q;
    cin >> n >> q;

    vvi queries;
    int t = 0;
    vector<vector<p2>> edges(n);
    vector<p2> edgelist;
    vvi e(n);
    rep(i, n + q - 1)
    {
        char c;
        cin >> c;
        if (c == 'S')
        {
            int a, b;
            cin >> a >> b;
            a--; b--;
            edgelist.push_back(p2(a, b));
            edges[a].push_back(p2(b, t));
            edges[b].push_back(p2(a, t));
            e[a].push_back(b);
            e[b].push_back(a);
            t++;
        }
        else if (c == 'Q')
        {
            int a, b;
            cin >> a >> b;
            a--; b--;
            queries.push_back({ 0, b, a, t - 1 });
        }
        else
        {
            int c;
            cin >> c;
            c--;
            queries.push_back({ 1, c, -1, t - 1 });
        }
    }
    depth[0] = 0;
    dfs(0, 0, -1, -1, edges);
    Centroid cent(e);

    auto getmax = [&](int a, int b)
    {
        return max(pathmax(a, b), pathmax(b, a));
    };

    auto getmin = [&](int a, int b)
    {
        return min(pathmin(a, b), pathmin(b, a));
    };

    auto pathgood = [&](int a, int b, int t)
    {
        if (getmax(a, b) > t) return false;
        // all edges <= t
        // from b->lca increasing
        // from a->lca decreasing
        bool good = 1;
        int u = b;
        int prev = inf;
        for (int d = 17; d >= 0; d--)
        {
            if (!isancestor(up[u][d], a))
            {
                good &= updecreasing[u][d];
                u = up[u][d];
            }
        }
        if (!isancestor(u, a))
        {
            prev = upmax[u][0];
        }


        u = a;
        int v = -1;
        for (int d = 17; d >= 0; d--)
        {
            if (!isancestor(up[u][d], b))
            {
                good &= upincreasing[u][d];
                u = up[u][d];
            }
        }
        if (!isancestor(u, b))
        {
            v = upmax[u][0];
        }

        return good && (v < prev);
    };

    vector<map<int, int>> children(n);
    vi sum(n);
    vvi blocked(n);
    rep(i, n)blocked[i].push_back(inf);
    vi parenton(n);
    vi centroidpar = cent.par;
    vvi centroidadj(n);
    rep(i, n)
    {
        if (centroidpar[i] == -1) continue;
        centroidadj[i].push_back(centroidpar[i]);
        centroidadj[centroidpar[i]].push_back(i);
    }
    Centroid c2(e);
    c2.vis = vi(n); c2.par = vi(n); c2.size = vi(n);
    c2.find_size(0, 0);
    int center = c2.find_centroid(0, 0, c2.size[0]);
    d(center, center, centroidadj);

    vector<vector<p2>> enableat(n + 2);
    rep(i, n)
    {
        int u = centroidpar[i];
        int prev = i;
        while (u != -1)
        {
            if (pathgood(u, i, inf)) enableat[getmax(u, i)].emplace_back(prev, getmin(i, u));
            prev = u;
            u = centroidpar[u];
        }
    }

    auto enable = [&](int ind)
    {
        int u = cdepth[edgelist[ind].first] > cdepth[edgelist[ind].second] ? edgelist[ind].first : edgelist[ind].second;
        int s = u;
        while (true)
        {
            if (centroidpar[u] == -1) break;
            //if (!pathgood(centroidpar[u],s,ind)) break;
            int pe = getmin(u, centroidpar[u]);
            repe(c, blocked[u])
            {
                if (c > pe)
                {
                    children[centroidpar[u]][pe]++;
                    blocked[centroidpar[u]].push_back(pe);
                }
            }
            blocked[u] = vi();
            u = centroidpar[u];
        }
    };

    int timer = 0;
    repe(q, queries)
    {
        int type = q[0], a = q[1], b = q[2], t = q[3];

        if (type == 0)
        {
            cout << (pathgood(a, b, t) ? "yes" : "no") << "\n";
        }
        else
        {

            while (timer <= t)
            {
                repe(e, enableat[timer])
                {
                    children[centroidpar[e.first]][e.second]++;
                }
                timer++;
            }

            int ans = 0;
            repe(c, children[a]) ans += c.second;
            int u = a;
            int prev = u;
            while (u != center)
            {
                prev = u;
                u = centroidpar[u];
                if (pathgood(a, u, t))
                {
                    ans++;// = depth[u] + depth[prev] - 2 * depth[lca(u, prev)];
                    int v = getmax(a, u);
                    repe(c, children[u]) if (c.first > v) ans += c.second;
                }

            }

            cout << ans + 1 << "\n";
        }
    }

    return 0;
}

Compilation message

servers.cpp: In constructor 'Centroid::Centroid(vvi&)':
servers.cpp:119:9: warning: 'Centroid::edges' will be initialized after [-Wreorder]
  119 |     vvi edges;
      |         ^~~~~
servers.cpp:118:9: warning:   'int Centroid::n' [-Wreorder]
  118 |     int n;
      |         ^
servers.cpp:125:5: warning:   when initialized here [-Wreorder]
  125 |     Centroid(vvi& edges) : edges(edges), n(edges.size()), vis(n), par(n), size(n)
      |     ^~~~~~~~
servers.cpp: In lambda function:
servers.cpp:311:13: warning: unused variable 's' [-Wunused-variable]
  311 |         int s = u;
      |             ^
servers.cpp: In function 'int main()':
servers.cpp:354:17: warning: variable 'prev' set but not used [-Wunused-but-set-variable]
  354 |             int prev = u;
      |                 ^~~~
servers.cpp:308:10: warning: variable 'enable' set but not used [-Wunused-but-set-variable]
  308 |     auto enable = [&](int ind)
      |          ^~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 17664 KB Output is correct
2 Correct 46 ms 21760 KB Output is correct
3 Correct 45 ms 21760 KB Output is correct
4 Correct 62 ms 21760 KB Output is correct
5 Correct 65 ms 22268 KB Output is correct
6 Correct 42 ms 21752 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 17664 KB Output is correct
2 Correct 46 ms 21760 KB Output is correct
3 Correct 45 ms 21760 KB Output is correct
4 Correct 62 ms 21760 KB Output is correct
5 Correct 65 ms 22268 KB Output is correct
6 Correct 42 ms 21752 KB Output is correct
7 Correct 34 ms 17664 KB Output is correct
8 Correct 64 ms 21704 KB Output is correct
9 Correct 190 ms 22780 KB Output is correct
10 Correct 104 ms 22540 KB Output is correct
11 Correct 146 ms 22980 KB Output is correct
12 Correct 772 ms 22784 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17676 KB Output is correct
2 Correct 289 ms 105036 KB Output is correct
3 Correct 233 ms 105120 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17676 KB Output is correct
2 Correct 289 ms 105036 KB Output is correct
3 Correct 233 ms 105120 KB Output is correct
4 Correct 32 ms 17572 KB Output is correct
5 Execution timed out 3535 ms 110128 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 18176 KB Output is correct
2 Correct 687 ms 123160 KB Output is correct
3 Correct 688 ms 124216 KB Output is correct
4 Correct 743 ms 132436 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 18176 KB Output is correct
2 Correct 687 ms 123160 KB Output is correct
3 Correct 688 ms 124216 KB Output is correct
4 Correct 743 ms 132436 KB Output is correct
5 Correct 32 ms 18444 KB Output is correct
6 Correct 979 ms 130012 KB Output is correct
7 Correct 1014 ms 137428 KB Output is correct
8 Correct 1089 ms 129152 KB Output is correct
9 Correct 1111 ms 129472 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 18436 KB Output is correct
2 Correct 369 ms 112180 KB Output is correct
3 Correct 398 ms 106552 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 18436 KB Output is correct
2 Correct 369 ms 112180 KB Output is correct
3 Correct 398 ms 106552 KB Output is correct
4 Correct 33 ms 18432 KB Output is correct
5 Correct 483 ms 117604 KB Output is correct
6 Correct 530 ms 112084 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18436 KB Output is correct
2 Correct 647 ms 124228 KB Output is correct
3 Correct 649 ms 124320 KB Output is correct
4 Correct 669 ms 132344 KB Output is correct
5 Correct 32 ms 18432 KB Output is correct
6 Correct 352 ms 112148 KB Output is correct
7 Correct 407 ms 106828 KB Output is correct
8 Correct 604 ms 107928 KB Output is correct
9 Correct 608 ms 107892 KB Output is correct
10 Correct 1136 ms 116864 KB Output is correct
11 Correct 1258 ms 114976 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18436 KB Output is correct
2 Correct 647 ms 124228 KB Output is correct
3 Correct 649 ms 124320 KB Output is correct
4 Correct 669 ms 132344 KB Output is correct
5 Correct 32 ms 18432 KB Output is correct
6 Correct 352 ms 112148 KB Output is correct
7 Correct 407 ms 106828 KB Output is correct
8 Correct 604 ms 107928 KB Output is correct
9 Correct 608 ms 107892 KB Output is correct
10 Correct 1136 ms 116864 KB Output is correct
11 Correct 1258 ms 114976 KB Output is correct
12 Correct 34 ms 18436 KB Output is correct
13 Correct 883 ms 129716 KB Output is correct
14 Correct 944 ms 137328 KB Output is correct
15 Correct 1053 ms 129804 KB Output is correct
16 Correct 1049 ms 129324 KB Output is correct
17 Correct 34 ms 18580 KB Output is correct
18 Correct 486 ms 118168 KB Output is correct
19 Correct 554 ms 112140 KB Output is correct
20 Correct 786 ms 113372 KB Output is correct
21 Correct 745 ms 113628 KB Output is correct
22 Correct 1632 ms 120048 KB Output is correct
23 Correct 1656 ms 126696 KB Output is correct
24 Correct 1456 ms 125376 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18384 KB Output is correct
2 Correct 47 ms 23032 KB Output is correct
3 Correct 44 ms 23040 KB Output is correct
4 Correct 61 ms 23104 KB Output is correct
5 Correct 67 ms 23548 KB Output is correct
6 Correct 43 ms 23432 KB Output is correct
7 Correct 35 ms 18364 KB Output is correct
8 Correct 286 ms 107864 KB Output is correct
9 Correct 283 ms 107636 KB Output is correct
10 Correct 29 ms 18444 KB Output is correct
11 Correct 659 ms 124512 KB Output is correct
12 Correct 708 ms 124276 KB Output is correct
13 Correct 751 ms 132552 KB Output is correct
14 Correct 32 ms 18444 KB Output is correct
15 Correct 434 ms 112376 KB Output is correct
16 Correct 483 ms 106804 KB Output is correct
17 Correct 694 ms 108152 KB Output is correct
18 Correct 692 ms 107988 KB Output is correct
19 Correct 1461 ms 116896 KB Output is correct
20 Correct 1440 ms 115412 KB Output is correct
21 Correct 306 ms 108380 KB Output is correct
22 Correct 262 ms 108768 KB Output is correct
23 Correct 355 ms 109916 KB Output is correct
24 Correct 361 ms 109724 KB Output is correct
25 Correct 834 ms 112472 KB Output is correct
26 Correct 466 ms 106940 KB Output is correct
27 Correct 420 ms 106944 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18384 KB Output is correct
2 Correct 47 ms 23032 KB Output is correct
3 Correct 44 ms 23040 KB Output is correct
4 Correct 61 ms 23104 KB Output is correct
5 Correct 67 ms 23548 KB Output is correct
6 Correct 43 ms 23432 KB Output is correct
7 Correct 35 ms 18364 KB Output is correct
8 Correct 286 ms 107864 KB Output is correct
9 Correct 283 ms 107636 KB Output is correct
10 Correct 29 ms 18444 KB Output is correct
11 Correct 659 ms 124512 KB Output is correct
12 Correct 708 ms 124276 KB Output is correct
13 Correct 751 ms 132552 KB Output is correct
14 Correct 32 ms 18444 KB Output is correct
15 Correct 434 ms 112376 KB Output is correct
16 Correct 483 ms 106804 KB Output is correct
17 Correct 694 ms 108152 KB Output is correct
18 Correct 692 ms 107988 KB Output is correct
19 Correct 1461 ms 116896 KB Output is correct
20 Correct 1440 ms 115412 KB Output is correct
21 Correct 306 ms 108380 KB Output is correct
22 Correct 262 ms 108768 KB Output is correct
23 Correct 355 ms 109916 KB Output is correct
24 Correct 361 ms 109724 KB Output is correct
25 Correct 834 ms 112472 KB Output is correct
26 Correct 466 ms 106940 KB Output is correct
27 Correct 420 ms 106944 KB Output is correct
28 Correct 35 ms 18436 KB Output is correct
29 Correct 69 ms 22936 KB Output is correct
30 Correct 197 ms 23108 KB Output is correct
31 Correct 109 ms 23236 KB Output is correct
32 Correct 150 ms 23404 KB Output is correct
33 Correct 787 ms 23016 KB Output is correct
34 Correct 42 ms 18624 KB Output is correct
35 Execution timed out 3520 ms 113136 KB Time limit exceeded
36 Halted 0 ms 0 KB -