oj.uz

Submission #86833

# Submission time Handle Problem Language Result Execution time Memory
86833 2018-11-27T17:08:41 Z karma Synchronization (JOI13_synchronization) C++14
100 / 100
 263 ms 17392 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2848 KB Output is correct
4 Correct 4 ms 2896 KB Output is correct
5 Correct 4 ms 2896 KB Output is correct
6 Correct 5 ms 2952 KB Output is correct
7 Correct 19 ms 3904 KB Output is correct
8 Correct 19 ms 3924 KB Output is correct
9 Correct 18 ms 4072 KB Output is correct
10 Correct 208 ms 12436 KB Output is correct
11 Correct 212 ms 12436 KB Output is correct
12 Correct 183 ms 16924 KB Output is correct
13 Correct 142 ms 16924 KB Output is correct
14 Correct 129 ms 16924 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 16924 KB Output is correct
2 Correct 98 ms 16924 KB Output is correct
3 Correct 88 ms 16924 KB Output is correct
4 Correct 94 ms 16924 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16924 KB Output is correct
2 Correct 4 ms 16924 KB Output is correct
3 Correct 4 ms 16924 KB Output is correct
4 Correct 4 ms 16924 KB Output is correct
5 Correct 4 ms 16924 KB Output is correct
6 Correct 5 ms 16924 KB Output is correct
7 Correct 19 ms 16924 KB Output is correct
8 Correct 196 ms 17164 KB Output is correct
9 Correct 196 ms 17392 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 17392 KB Output is correct
2 Correct 105 ms 17392 KB Output is correct
3 Correct 119 ms 17392 KB Output is correct
4 Correct 118 ms 17392 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17392 KB Output is correct
2 Correct 4 ms 17392 KB Output is correct
3 Correct 4 ms 17392 KB Output is correct
4 Correct 5 ms 17392 KB Output is correct
5 Correct 5 ms 17392 KB Output is correct
6 Correct 22 ms 17392 KB Output is correct
7 Correct 263 ms 17392 KB Output is correct
8 Correct 220 ms 17392 KB Output is correct
9 Correct 226 ms 17392 KB Output is correct
10 Correct 183 ms 17392 KB Output is correct
11 Correct 124 ms 17392 KB Output is correct
12 Correct 161 ms 17392 KB Output is correct
13 Correct 102 ms 17392 KB Output is correct