oj.uz

Submission #86841

# Submission time Handle Problem Language Result Execution time Memory
86841 2018-11-27T18:47:35 Z long10024070 Synchronization (JOI13_synchronization) C++11
50 / 100
 229 ms 19244 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)
{
//    cout << id << ' ' << st[id] << ' ' << en[id] << '\n';
    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);
//        cout << x << '\n';
        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 = Query(1,_u[i]);
//        cout << _v[i] << ' ' << cp << '\n';
        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;
//        cout << f[cp] << '\n';
    }
    for (int i=1;i<=n;++i)
        if (b[i]) {
            int cp = 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Incorrect 4 ms 2940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 15652 KB Output is correct
2 Correct 143 ms 15652 KB Output is correct
3 Correct 122 ms 18552 KB Output is correct
4 Correct 121 ms 18552 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18552 KB Output is correct
2 Correct 5 ms 18552 KB Output is correct
3 Correct 4 ms 18552 KB Output is correct
4 Correct 4 ms 18552 KB Output is correct
5 Correct 4 ms 18552 KB Output is correct
6 Correct 5 ms 18552 KB Output is correct
7 Correct 21 ms 18552 KB Output is correct
8 Correct 214 ms 18924 KB Output is correct
9 Correct 229 ms 18924 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 18956 KB Output is correct
2 Correct 142 ms 19244 KB Output is correct
3 Correct 143 ms 19244 KB Output is correct
4 Correct 141 ms 19244 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19244 KB Output is correct
2 Incorrect 4 ms 19244 KB Output isn't correct
3 Halted 0 ms 0 KB -