oj.uz

Submission #86935

# Submission time Handle Problem Language Result Execution time Memory
86935 2018-11-28T16:26:40 Z long10024070 Synchronization (JOI13_synchronization) C++11
100 / 100
 355 ms 19328 KB 
#define Link "https://oj.uz/problem/view/JOI13_synchronization?fbclid=IwAR13-gsTQ4n3SSIS6NzUA_X7iaFxN_3aJYCyIeVRZb88iIzHhvMV6K31H-M"

#include <iostream>
#include <cstdio>
#include <vector>

#define TASK "Synchronization"

using namespace std;

const int maxn = 1e5 + 1;
int n,m,q,_u[maxn],_v[maxn],h[maxn],st[maxn],en[maxn],cnt,True[maxn],f[maxn],mem[maxn];
vector <int> e[maxn];
struct T_node
{
    int l,r,mx;
} node[maxn*6];
bool b[maxn];

void Enter()
{
    cin >> n >> m >> q;
    for (int i=1;i<n;++i) {
        cin >> _u[i] >> _v[i];
        e[_u[i]].push_back(_v[i]);
        e[_v[i]].push_back(_u[i]);
    }
}

void DFS(int u, int p)
{
    h[u] = h[p] + 1;
    st[u] = en[u] = ++cnt;
    True[st[u]] = u;
    for (int v : e[u])
        if (v != p) {
            DFS(v,u);
            en[u] = en[v];
        }
}

void Init()
{
    DFS(1,0);
    for (int i=1;i<=n;++i)
        if (h[_u[i]] > h[_v[i]])
            swap(_u[i],_v[i]);
}

void Build_tree(int i, int l, int r)
{
    node[i].l = l;
    node[i].r = r;
    if (l != r) {
        Build_tree(i*2,l,(l+r)/2);
        Build_tree(i*2+1,(l+r)/2+1,r);
        node[i].mx = max(node[i*2].mx,node[i*2+1].mx);
    }
    else
        node[i].mx = en[True[l]];
}

int Query(int i, int id)
{
    if (st[id] < node[i].l || node[i].mx < en[id])
        return 0;
    if (node[i].l == node[i].r)
        return node[i].l;
    else {
        int x = Query(i*2+1,id);
        if (x != 0)
            return x;
        return Query(i*2,id);
    }
}

void Update(int i, int id, int val)
{
    if (node[i].r < id || id < node[i].l)
        return;
    if (node[i].l == node[i].r)
        node[i].mx = val;
    else {
        Update(i*2,id,val);
        Update(i*2+1,id,val);
        node[i].mx = max(node[i*2].mx,node[i*2+1].mx);
    }
}

void Solve()
{
    fill(f,f+n+1,1);
    Build_tree(1,1,n);
    for (;m>0;--m) {
        int i;
        cin >> i;
        int cp = True[Query(1,_u[i])];
        if (b[i]) {
            f[_v[i]] = mem[_v[i]] = f[cp];
            Update(1,st[_v[i]],en[_v[i]]);
        }
        else {
            f[cp] += f[_v[i]] - mem[_v[i]];
            Update(1,st[_v[i]],0);
        }
        b[i] ^= 1;
    }
    for (int i=1;i<=n;++i)
        if (b[i]) {
            int cp = True[Query(1,_u[i])];
            Update(1,st[_v[i]],en[_v[i]]);
            f[_v[i]] = mem[_v[i]] = f[cp];
            b[i] = 0;
        }
    for (;q>0;--q) {
        int u;
        cin >> u;
        cout << f[u] << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

#ifdef LHL
    freopen(".INP","r",stdin);
    freopen(".OUT","w",stdout);
#else
//    freopen(TASK".INP","r",stdin);
//    freopen(TASK".OUT","w",stdout);
#endif // LHL

    Enter();
    Init();
    Solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2684 KB Output is correct
2 Correct 4 ms 2804 KB Output is correct
3 Correct 4 ms 2880 KB Output is correct
4 Correct 4 ms 2956 KB Output is correct
5 Correct 4 ms 3032 KB Output is correct
6 Correct 5 ms 3036 KB Output is correct
7 Correct 22 ms 3932 KB Output is correct
8 Correct 21 ms 3932 KB Output is correct
9 Correct 22 ms 3932 KB Output is correct
10 Correct 258 ms 12524 KB Output is correct
11 Correct 265 ms 12528 KB Output is correct
12 Correct 282 ms 18668 KB Output is correct
13 Correct 210 ms 18668 KB Output is correct
14 Correct 222 ms 18668 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 18668 KB Output is correct
2 Correct 150 ms 18668 KB Output is correct
3 Correct 160 ms 18668 KB Output is correct
4 Correct 126 ms 18668 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18668 KB Output is correct
2 Correct 5 ms 18668 KB Output is correct
3 Correct 4 ms 18668 KB Output is correct
4 Correct 4 ms 18668 KB Output is correct
5 Correct 4 ms 18668 KB Output is correct
6 Correct 6 ms 18668 KB Output is correct
7 Correct 24 ms 18668 KB Output is correct
8 Correct 241 ms 18820 KB Output is correct
9 Correct 253 ms 18840 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 18972 KB Output is correct
2 Correct 143 ms 19152 KB Output is correct
3 Correct 148 ms 19328 KB Output is correct
4 Correct 149 ms 19328 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19328 KB Output is correct
2 Correct 4 ms 19328 KB Output is correct
3 Correct 4 ms 19328 KB Output is correct
4 Correct 4 ms 19328 KB Output is correct
5 Correct 6 ms 19328 KB Output is correct
6 Correct 25 ms 19328 KB Output is correct
7 Correct 355 ms 19328 KB Output is correct
8 Correct 236 ms 19328 KB Output is correct
9 Correct 208 ms 19328 KB Output is correct
10 Correct 238 ms 19328 KB Output is correct
11 Correct 199 ms 19328 KB Output is correct
12 Correct 171 ms 19328 KB Output is correct
13 Correct 148 ms 19328 KB Output is correct