oj.uz

Submission #544548

# Submission time Handle Problem Language Result Execution time Memory
544548 2022-04-02T09:34:42 Z iulia13 Synchronization (JOI13_synchronization) C++14
100 / 100
 817 ms 40332 KB 
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
const int LG = 20;
vector <int> g[N];
int dad[N][LG];
map <int, int> id[N];
int lvl[N], in[N], out[N], timp, card[N], inters[N], aib[N], n;
int lsb(int x)
{
    return x & (-x);
}
void upd(int x, int val)
{
    for (x; x <= n; x += lsb(x))
        aib[x] += val;
}
int qry(int x)
{
    int ans = 0;
    for (x; x; x -= lsb(x))
        ans += aib[x];
    return ans;
}
void lifting() ///used
{
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i <= n; i++)
            dad[i][j] = dad[dad[i][j - 1]][j - 1];
}
int lca(int x, int y)
{
    int lg = 19;
    while (lvl[x] < lvl[y])
    {
        if (lvl[x] <= lvl[dad[y][lg]])
            y = dad[y][lg];
        lg--;
    }
    lg = 19;
    while (lvl[x] > lvl[y])
    {
        if (lvl[y] <= lvl[dad[x][lg]])
            x = dad[x][lg];
        lg--;
    }
    lg = 19;
    while (x != y && lg > -1)
    {
        if(dad[x][lg] != dad[y][lg])
        {
            x = dad[x][lg];
            y = dad[y][lg];
        }
        lg--;
    }
    if (x != y)
        return dad[x][0];
    return x;
}
int nrm;
void dfs(int nod)
{
    in[nod] = ++timp;
    for (auto son : g[nod])
    {
        if (son == dad[nod][0])
            continue;
        dad[son][0] = nod;
        ///id[nod][son] = ++nrm;
        lvl[son] = lvl[nod] + 1;
        dfs(son);
    }
    out[nod] = timp;
}
int label(int u)
{
    if (u == 0)
        return -1;
    return qry(in[u]);
}
bool queryJoined(int u, int v)
{
    int p = dad[v][0];
    return (label(u) - label(p) == lvl[u] - lvl[p]);
}
int queryCCRep(int u)
{
    int lg = 19, v = u;
    while (0 <= lg)
    {
        int dadv = dad[v][lg];
        if (dadv && queryJoined(u, dadv))
            v = dadv;
        lg--;
    }
    if (v != 1 && queryJoined(u, v))
        v = dad[v][0];
    return v;
}
void initEdges()
{
    for (int i = 1; i <= n; i++)
    {
        //upd(i, 1);
        card[i] = 1;
    }
}
void splitEdge(int u, int v) ///u == dad[v][0]
{
    int root = queryCCRep(u);
    inters[id[u][v]] = card[root];
    card[v] = card[root];
    upd(in[v], -1);
    upd(out[v] + 1, 1);
}
void joinEdge(int u, int v) ///u == dad[v][0]
{
    int root = queryCCRep(u);
    card[root] = card[root] + card[v] - inters[id[u][v]];
    upd(in[v], 1);
    upd(out[v] + 1, -1);
}
int queryVertex(int u)
{
    return card[queryCCRep(u)];
}
bool edgestate[N];
pair <int, int> edges[N];
int main()
{
    int m, q;
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
        id[a][b] = id[b][a] = i;
        edges[i] = {a, b};
        edgestate[i] = false;
    }
    lvl[1] = 1;
    dfs(1);
    lifting();
    initEdges();
    for (int i = 1; i <= m; i++)
    {
        int a, b, e;
        cin >> e;
        a = edges[e].first;
        b = edges[e].second;
        if (dad[a][0] == b)
            swap(a, b);
        if (edgestate[id[a][b]] == false)
        {
            edgestate[id[a][b]] = true;
            joinEdge(a, b);
        }
        else
        {
            edgestate[id[a][b]] = false;
            splitEdge(a, b);
        }
    }
    for (int i = 1; i <= q; i++)
    {
        int a;
        cin >> a;
        cout << queryVertex(a) << '\n';
    }
    return 0;
}

Compilation message

synchronization.cpp: In function 'void upd(int, int)':
synchronization.cpp:16:10: warning: statement has no effect [-Wunused-value]
   16 |     for (x; x <= n; x += lsb(x))
      |          ^
synchronization.cpp: In function 'int qry(int)':
synchronization.cpp:22:10: warning: statement has no effect [-Wunused-value]
   22 |     for (x; x; x -= lsb(x))
      |          ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7360 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 6 ms 7628 KB Output is correct
7 Correct 25 ms 9932 KB Output is correct
8 Correct 25 ms 9940 KB Output is correct
9 Correct 27 ms 9928 KB Output is correct
10 Correct 435 ms 33308 KB Output is correct
11 Correct 478 ms 33356 KB Output is correct
12 Correct 601 ms 39464 KB Output is correct
13 Correct 363 ms 33240 KB Output is correct
14 Correct 299 ms 32356 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 35932 KB Output is correct
2 Correct 190 ms 35656 KB Output is correct
3 Correct 212 ms 38576 KB Output is correct
4 Correct 206 ms 38484 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7360 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 8 ms 7624 KB Output is correct
7 Correct 50 ms 10580 KB Output is correct
8 Correct 817 ms 40220 KB Output is correct
9 Correct 772 ms 40332 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 40268 KB Output is correct
2 Correct 437 ms 39472 KB Output is correct
3 Correct 414 ms 39616 KB Output is correct
4 Correct 413 ms 39712 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7356 KB Output is correct
5 Correct 8 ms 7632 KB Output is correct
6 Correct 47 ms 10136 KB Output is correct
7 Correct 665 ms 34192 KB Output is correct
8 Correct 817 ms 40232 KB Output is correct
9 Correct 530 ms 34364 KB Output is correct
10 Correct 478 ms 33612 KB Output is correct
11 Correct 372 ms 37092 KB Output is correct
12 Correct 378 ms 37152 KB Output is correct
13 Correct 409 ms 39664 KB Output is correct