oj.uz

Submission #751006

# Submission time Handle Problem Language Result Execution time Memory
751006 2023-05-30T19:13:30 Z anaduguleanu Synchronization (JOI13_synchronization) C++14
100 / 100
 650 ms 23240 KB 
#include <iostream>
#include <vector>
#define MAX 100000
#define LOG 20
using namespace std;
///ifstream cin ("c.in");
///ofstream cout ("c.out");
vector <int> graph[MAX + 10];
pair <int, int> edges[2 * MAX + 10];
int timer = 1, in[MAX + 10], out[MAX + 10], ancestor[LOG + 10][MAX + 10], tree[MAX + 10], info[MAX + 10], last[MAX + 10], active[MAX + 10];
void update(int pos, int val)
{
    for (int i = pos; i <= MAX; i = i + (i & -i))
        tree[i] = tree[i] + val;
}
int query(int pos)
{
    int ans = 0;
    for (int i = pos; i >= 1; i = i - (i & -i))
        ans = ans + tree[i];
    return ans;
}
void dfs(int node, int parent)
{
    ancestor[0][node] = parent;
    for (int p = 1; p <= LOG && ancestor[p - 1][node] != 0; p++)
        ancestor[p][node] = ancestor[p - 1][ancestor[p - 1][node]];
    info[node] = 1;
    in[node] = timer;
    timer++;
    for (auto next : graph[node])
        if (next != parent)
            dfs(next, node);
    out[node] = timer;
}
int findAncestor(int node)
{
    for (int p = LOG; p >= 0; p--)
        if (ancestor[p][node] != 0 && query(in[ancestor[p][node]]) == query(in[node]))
            node = ancestor[p][node];
    return node;
}
int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
        edges[i] = {x, y};
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
    {
        update(in[i], -1);
        update(out[i], 1);
    }
    for (int i = 1; i <= m; i++)
    {
        int edge;
        cin >> edge;
        int node1 = edges[edge].first, node2 = edges[edge].second;
        if (ancestor[0][node1] == node2)
            swap(node1, node2);
        if (active[edge] == 1)
        {
            info[node2] = last[node2] = info[findAncestor(node1)];
            update(in[node2], -1);
            update(out[node2], 1);
            active[edge] = 0;
        }
        else
        {
            info[findAncestor(node1)] = info[findAncestor(node1)] + info[node2] - last[node2];
            update(in[node2], 1);
            update(out[node2], -1);
            active[edge] = 1;
        }
    }
    for (int i = 1; i <= q; i++)
    {
        int node;
        cin >> node;
        cout << info[findAncestor(node)] << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2732 KB Output is correct
7 Correct 18 ms 3792 KB Output is correct
8 Correct 18 ms 3668 KB Output is correct
9 Correct 18 ms 3668 KB Output is correct
10 Correct 220 ms 13644 KB Output is correct
11 Correct 242 ms 13676 KB Output is correct
12 Correct 456 ms 22632 KB Output is correct
13 Correct 128 ms 12020 KB Output is correct
14 Correct 187 ms 13088 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 18140 KB Output is correct
2 Correct 145 ms 17972 KB Output is correct
3 Correct 151 ms 21692 KB Output is correct
4 Correct 160 ms 21544 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 6 ms 2900 KB Output is correct
7 Correct 41 ms 4608 KB Output is correct
8 Correct 631 ms 23240 KB Output is correct
9 Correct 636 ms 23160 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 23140 KB Output is correct
2 Correct 362 ms 22632 KB Output is correct
3 Correct 351 ms 22648 KB Output is correct
4 Correct 345 ms 22732 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 6 ms 2772 KB Output is correct
6 Correct 35 ms 3796 KB Output is correct
7 Correct 401 ms 14780 KB Output is correct
8 Correct 640 ms 23216 KB Output is correct
9 Correct 326 ms 13108 KB Output is correct
10 Correct 314 ms 13896 KB Output is correct
11 Correct 299 ms 19404 KB Output is correct
12 Correct 294 ms 19392 KB Output is correct
13 Correct 351 ms 22724 KB Output is correct