Submission #86833

#	Time	Username	Problem	Language	Result	Execution time	Memory
86833		karma	Synchronization (JOI13_synchronization)	C++14	100 / 100	263 ms	17392 KiB

synchronization

#include<bits/stdc++.h>
#define For(i, a, b)  for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define FileName      "test"
#define ll            long long
#define ld            long double
#define ull           unsigned long long
#define pb            push_back
#define X             first
#define Y             second
//#define Karma

using namespace std;

template <typename T> inline void Cin(T &x)
{
    char c;
    T sign = 1;
    x = 0;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        if (c == '-') sign = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= sign;
}

template <typename T> inline void Out(T x)
{
    if(x > 9) Out(x / 10);
    putchar(x % 10 + '0');
}

template <typename T> inline void Cout(T x)
{
    if (x < 0) putchar('-'), x = -x;
    Out(x);
    putchar('\n');
}

typedef pair<int, int> pii;
typedef pair<ll, int> plli;
const int N = 1e5 + 7;
const int M = 4e5 + 7;

struct TEdge{int u, v;} e[N];
int l[M], h[M], st[N], en[N], p[N], node[M], On[N], root;
int n, nUpdate, nQuery, x, Time = 0, res[N], last[N], id;
vector<int> a[N];

void DFS(int u, int par)
{
    st[u] = ++Time;
    p[Time] = u, res[u] = 1;
    for(int i: a[u])
    {
        int v = e[i].u + e[i].v - u;
        if(v == par) continue;
        if(e[i].u != u) swap(e[i].u, e[i].v);
        DFS(v, u);
    }
    en[u] = Time;
}

void Enter()
{
     Cin(n), Cin(nUpdate), Cin(nQuery);
     For(i, 1, n - 1)
     {
         Cin(e[i].u), Cin(e[i].v);
         a[e[i].u].pb(i), a[e[i].v].pb(i);
     }
     DFS(1, 1);
}

void Build(int x, int low, int high)
{
    l[x] = low, h[x] = high;
    if(l[x] == h[x])
    {
        node[x] = en[p[low]];
        return;
    }
    int mid = (low + high) >> 1;
    Build(2 * x, low, mid);
    Build(2 * x + 1, mid + 1, high);
    node[x] = max(node[2 * x], node[2 * x + 1]);
}

void Update(int x, int pos, int val)
{
     if(l[x] > pos || h[x] < pos) return;
     if(l[x] == pos && h[x] == pos)
     {
         node[x] = val;
         return;
     }
     Update(2 * x, pos, val);
     Update(2 * x + 1, pos, val);
     node[x] = max(node[2 * x], node[2 * x + 1]);
}

int Query(int x, int pos, int val)
{
    if(l[x] > pos || node[x] < val) return -1;
    if(l[x] == h[x]) return p[l[x]];
    int res = Query(2 * x + 1, pos, val);
    if(res != -1) return res;
    return Query(2 * x, pos, val);
}

void Solve()
{
     Build(1, 1, n);
     while(nUpdate --)
     {
         Cin(id);
         root = Query(1, st[e[id].u], en[e[id].u]);
         if(On[id])
         {
            res[e[id].v] = last[e[id].v] = res[root];
            Update(1, st[e[id].v], en[e[id].v]);
         }
         else
         {
            res[root] += res[e[id].v] - last[e[id].v];
            Update(1, st[e[id].v], -1);
         }
         On[id] ^= 1;
     }
     while(nQuery --)
     {
         Cin(x);
         Cout(res[Query(1, st[x], en[x])]);
     }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
#ifdef Karma
    freopen(FileName".inp", "r", stdin);
    freopen(FileName".out", "w", stdout);
#endif // Karma

    Enter();
    Solve();

    return 0;
}

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