Submission #94951

#	Time	Username	Problem	Language	Result	Execution time	Memory
94951		bogdan10bos	Synchronization (JOI13_synchronization)	C++14	100 / 100	864 ms	24028 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40