Submission #544548

#	Time	Username	Problem	Language	Result	Execution time	Memory
544548		iulia13	Synchronization (JOI13_synchronization)	C++14	100 / 100	817 ms	40332 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40