제출 #1163126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163126		cpismylifeOwO	동기화 (JOI13_synchronization)	C++20	100 / 100	264 ms	45864 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;
const int MaxLog = 20;

struct Edge
{
    int u, v, pre;
    bool open;
};

int n, m, q;
Edge edges[MaxN];
vector<int> graph[MaxN];

void Inp()
{
    cin >> n >> m >> q;
    for (int x = 1; x < n; x++)
    {
        cin >> edges[x].u >> edges[x].v;
        edges[x].pre = edges[x].open = 0;
        graph[edges[x].u].push_back(x);
        graph[edges[x].v].push_back(x);
    }
}

int curDFS;
int in[MaxN];
int out[MaxN];
int h[MaxN];
int par[MaxN];

void PreDFS(int u, int p)
{
    curDFS++;
    in[u] = curDFS;
    for (int x : graph[u])
    {
        int v = edges[x].u ^ edges[x].v ^ u;
        if (v != p)
        {
            if (edges[x].u == v)
            {
                swap(edges[x].u, edges[x].v);
            }
            h[v] = h[u] + 1;
            par[v] = u;
            PreDFS(v, u);
        }
    }
    out[u] = curDFS;
}

int Fenwick[MaxN];
int BinLift[MaxLog][MaxN];

void Build()
{
    for (int x = 1; x <= n; x++)
    {
        BinLift[0][x] = par[x];
    }
    for (int x = 1; x < MaxLog; x++)
    {
        for (int y = 1; y <= n; y++)
        {
            BinLift[x][y] = BinLift[x - 1][BinLift[x - 1][y]];
        }
    }
}

void Add(int u, int delta)
{
    int idx = u;
    while (idx <= n)
    {
        Fenwick[idx] += delta;
        idx += (idx & (-idx));
    }
}

int Get(int u)
{
    int idx = u, res = 0;
    while (idx > 0)
    {
        res += Fenwick[idx];
        idx -= (idx & (-idx));
    }
    return res;
}

int cnt[MaxN];

int FindPar(int u)
{
    int cur = Get(in[u]), v = u;
    for (int x = MaxLog - 1; x >= 0; x--)
    {
        if (BinLift[x][v] > 0 && Get(in[BinLift[x][v]]) == cur)
        {
            v = BinLift[x][v];
        }
    }
    return v;
}

void Link(int id)
{
    int u = FindPar(edges[id].u), v = edges[id].v;
    cnt[u] = cnt[u] + cnt[v] - edges[id].pre;
    cnt[v] = 0;
    Add(in[v], -1);
    Add(out[v] + 1, 1);
}

void Cut(int id)
{
    int u = FindPar(edges[id].u), v = edges[id].v;
    cnt[v] = cnt[u];
    edges[id].pre = cnt[u];
    Add(in[v], 1);
    Add(out[v] + 1, -1);
}

void Exc()
{
    PreDFS(1, -1);
    Build();
    for (int x = 1; x <= n; x++)
    {
        cnt[x] = 1;
        Add(in[x], (x > 1));
        Add(out[x] + 1, -(x > 1));
    }
    for (int x = 1; x <= m; x++)
    {
        int u;
        cin >> u;
        edges[u].open ^= 1;
        if (edges[u].open)
        {
            Link(u);
        }
        else
        {
            Cut(u);
        }
    }
    for (int x = 1; x <= q; x++)
    {
        int u;
        cin >> u;
        cout << cnt[FindPar(u)] << "\n";
    }
}

int main()
{
    //freopen("C.INP", "r", stdin);
    //freopen("C.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40