oj.uz

Submission #544528

# Submission time Handle Problem Language Result Execution time Memory
544528 2022-04-02T08:41:54 Z iulia13 Synchronization (JOI13_synchronization) C++14
30 / 100
 579 ms 40308 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) 
{
    return (label(u) == label(v) && label(u) == label(lca(u, v)));
}
int queryCCRep(int u)
{
    int lg = 19;
    while (0 <= lg)
    {
        if (label(u) == label(dad[u][lg]))
            u = dad[u][lg];
        lg--;
    }
    return u;
}
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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Incorrect 4 ms 7360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 201 ms 35916 KB Output isn't correct
2 Halted 0 ms 0 KB -

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 4 ms 7364 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 7 ms 7632 KB Output is correct
7 Correct 48 ms 10708 KB Output is correct
8 Correct 579 ms 40192 KB Output is correct
9 Correct 579 ms 40224 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 40308 KB Output is correct
2 Correct 389 ms 39500 KB Output is correct
3 Correct 389 ms 39736 KB Output is correct
4 Correct 405 ms 39680 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Incorrect 4 ms 7380 KB Output isn't correct
3 Halted 0 ms 0 KB -