oj.uz

Submission #94951

# Submission time Handle Problem Language Result Execution time Memory
94951 2019-01-25T13:50:35 Z bogdan10bos Synchronization (JOI13_synchronization) C++14
100 / 100
 864 ms 24028 KB 
#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

const int NMAX = 1e5;
const int LG = 16;

typedef pair<int, int> pii;

int N, M, Q, I;
int f[LG + 2][NMAX + 5], h[NMAX + 5], itv[NMAX + 5][2], state[NMAX + 5];
int info[NMAX + 5], lst[NMAX + 5];
pii edge[NMAX + 5];
vector<int> edg[NMAX + 5];

void DFS(int nod, int fth)
{
    h[nod] = h[fth] + 1;
    f[0][nod] = fth;
    for(int i = 1; i <= LG; i++)
        f[i][nod] = f[i - 1][ f[i - 1][nod] ];

    itv[nod][0] = ++I;
    for(auto nxt: edg[nod])
        if(nxt != fth)
            DFS(nxt, nod);
    itv[nod][1] = I;
}

class BinaryIndexedTree
{
public:
    int aib[NMAX + 5];

    void U(int pos, int val)
    {
        for(; pos <= N; pos += (pos & (-pos)))
            aib[pos] += val;
    }

    int Q(int pos)
    {
        int ans = 0;
        for(; pos > 0; pos -= (pos & (-pos)))
            ans += aib[pos];
        return ans;
    }
}aib;

int getup(int nod)
{
    for(int i = LG; i >= 0; i--)
        if(f[i][nod] != 0)
        {
            if(aib.Q(itv[nod][0]) - aib.Q(itv[f[i][nod]][0]) == h[nod] - h[ f[i][nod] ])
                nod = f[i][nod];
        }
    return nod;
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d%d", &N, &M, &Q);
    for(int i = 1; i < N; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        edg[x].push_back(y);
        edg[y].push_back(x);
        edge[i] = {x, y};
    }

    DFS(1, 0);

    for(int i = 1; i <= N; i++)
    {
        info[i] = 1;
        lst[i] = 0;
    }

    for(int i = 1; i <= M; i++)
    {
        int id;
        scanf("%d", &id);
        int x = edge[id].first, y = edge[id].second;
        if(f[0][x] == y)   swap(x, y);
        int sup = getup(x);

        if(state[id] == 0)
        {
            aib.U(itv[y][0], 1);
            aib.U(itv[y][1] + 1, - 1);
            info[sup] += (info[y] - lst[y]);
        }
        else if(state[id] == 1)
        {
            aib.U(itv[y][0], -1);
            aib.U(itv[y][1] + 1, 1);
            lst[y] = info[y] = info[sup];
        }

        state[id] ^= 1;
    }

    for(int i = 1; i <= Q; i++)
    {
        int x;
        scanf("%d", &x);
        int nod = getup(x);
        printf("%d\n", info[nod]);
    }

    return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &M, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
synchronization.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &id);
         ~~~~~^~~~~~~~~~~
synchronization.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2824 KB Output is correct
2 Correct 25 ms 2808 KB Output is correct
3 Correct 3 ms 2824 KB Output is correct
4 Correct 4 ms 2756 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 5 ms 2920 KB Output is correct
7 Correct 18 ms 4344 KB Output is correct
8 Correct 19 ms 4344 KB Output is correct
9 Correct 19 ms 4344 KB Output is correct
10 Correct 346 ms 18680 KB Output is correct
11 Correct 279 ms 18424 KB Output is correct
12 Correct 548 ms 22948 KB Output is correct
13 Correct 89 ms 18344 KB Output is correct
14 Correct 176 ms 17980 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 20656 KB Output is correct
2 Correct 88 ms 20344 KB Output is correct
3 Correct 109 ms 22392 KB Output is correct
4 Correct 109 ms 22388 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2936 KB Output is correct
2 Correct 3 ms 2808 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 3 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 6 ms 2936 KB Output is correct
7 Correct 28 ms 4856 KB Output is correct
8 Correct 663 ms 24028 KB Output is correct
9 Correct 606 ms 23896 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 23800 KB Output is correct
2 Correct 181 ms 23532 KB Output is correct
3 Correct 178 ms 23628 KB Output is correct
4 Correct 182 ms 23672 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2720 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 2940 KB Output is correct
6 Correct 22 ms 4444 KB Output is correct
7 Correct 318 ms 19448 KB Output is correct
8 Correct 864 ms 23900 KB Output is correct
9 Correct 135 ms 19440 KB Output is correct
10 Correct 278 ms 19156 KB Output is correct
11 Correct 135 ms 21688 KB Output is correct
12 Correct 124 ms 21720 KB Output is correct
13 Correct 175 ms 23596 KB Output is correct