Submission #94941

#	Time	Username	Problem	Language	Result	Execution time	Memory
94941		alexpetrescu	Special graph (IZhO13_specialg)	C++14	100 / 100	90 ms	16120 KiB

specialg

#include <cstdio>
#include <vector>
#include <cstring>

//FILE *fin = fopen("specialg.in", "r"), *fout = fopen("specialg.out", "w");
#define fin stdin
#define fout stdout

#define MAXN 100000

std::vector < int > g[MAXN + 1];
int viz[MAXN + 1], unde[MAXN + 1], l[MAXN + 1], r[MAXN + 1], t[MAXN + 1];
int *aib[2 * MAXN + 1], h[MAXN + 1], k, ciclu[MAXN + 1], pozitie[MAXN + 1];
int lungime[2 * MAXN + 1], lider, care[2 * MAXN + 1], cate[2 * MAXN + 1];

inline void updateAib(int v[], int n, int p, int add) {
    while (p <= n) {
        v[p] += add;
        p += p & (-p);
    }
}

inline int queryAib(int v[], int p) {
    int ans = 0;
    while (p > 0) {
        ans += v[p];
        p -= p & (-p);
    }
    return ans;
}

inline void update(int x) {
    if (ciclu[x])
        updateAib(aib[ciclu[x]], lungime[ciclu[x]], pozitie[x], 1);
    else
        updateAib(aib[unde[x]], cate[unde[x]], l[x], 1), updateAib(aib[unde[x]], cate[unde[x]], r[x], -1);
}

int query(int x, int y) {
    if (ciclu[x]) {
        if (ciclu[y] != ciclu[x])
            return -1;
        if (pozitie[x] <= pozitie[y]) {
            if (queryAib(aib[ciclu[x]], pozitie[y] - 1) - queryAib(aib[ciclu[x]], pozitie[x] - 1) > 0)
                return -1;
            else
                return pozitie[y] - pozitie[x];
        } else {
            if (queryAib(aib[ciclu[x]], lungime[ciclu[x]]) - queryAib(aib[ciclu[x]], pozitie[x] - 1) + queryAib(aib[ciclu[x]], pozitie[y] - 1) > 0)
                return -1;
            else
                return lungime[ciclu[x]] - pozitie[x] + pozitie[y];
        }
    } else if (ciclu[y]) {
        int u = query(care[unde[x]], y);
        if (u == -1)
            return -1;
        if (queryAib(aib[unde[x]], l[x]) > 0)
            return -1;
        return h[x] + u;
    } else if (l[y] <= l[x] && r[x] <= r[y] && unde[x] == unde[y] && queryAib(aib[unde[x]], l[x]) - queryAib(aib[unde[x]], l[y]) == 0)
        return h[x] - h[y];
    else
        return -1;
}

void dfs(int x) {
    viz[x] = 2;
    unde[x] = lider;
    l[x] = ++k;
    for (auto &y : g[x]) {
        if (viz[y] != 2) {
            h[y] = h[x] + 1;
            dfs(y);
        }
    }
    r[x] = ++k;
}

int main() {
    int n;
    fscanf(fin, "%d", &n);

    for (int i = 1; i <= n; i++) {
        fscanf(fin, "%d", &t[i]);
        if (t[i] == 0)
            t[i] = i;
        g[t[i]].push_back(i);
    }

    int nr = 0;
    for (int i = 1; i <= n; i++) {
        if (viz[i] == 0) {
            int x = i;
            while (viz[x] == 0) {
                viz[x] = 1;
                x = t[x];
            }

            nr++;
            int poz = 0;
            while (viz[x] == 1) {
                viz[x] = 2;
                ciclu[x] = nr;
                poz++;
                pozitie[x] = poz;
                x = t[x];
            }
            lungime[nr] = poz;
            aib[nr] = new int[lungime[nr] + 1];
            memset(aib[nr], 0, sizeof(int) * (lungime[nr] + 1));

            do {
                nr++;
                lider = nr;
                care[nr] = x;
                k = 0;
                dfs(x);
                cate[nr] = k;
                aib[nr] = new int[k + 1];
                memset(aib[nr], 0, sizeof(int) * (k + 1));
                x = t[x];
            } while (pozitie[x] != 1);
        }
    }

    int q;
    fscanf(fin, "%d", &q);

    for (; q; q--) {
        int t;
        fscanf(fin, "%d", &t);

        if (t == 1) {
            int x;
            fscanf(fin, "%d", &x);

            update(x);
        } else {
            int x, y;
            fscanf(fin, "%d%d", &x, &y);

            fprintf(fout, "%d\n", query(x, y));
        }
    }

    fclose(fin);
    fclose(fout);
    return 0;
}

Compilation message (stderr)

specialg.cpp: In function 'int main()':
specialg.cpp:82:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fin, "%d", &n);
     ~~~~~~^~~~~~~~~~~~~~~
specialg.cpp:85:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(fin, "%d", &t[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~~
specialg.cpp:128:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fin, "%d", &q);
     ~~~~~~^~~~~~~~~~~~~~~
specialg.cpp:132:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(fin, "%d", &t);
         ~~~~~~^~~~~~~~~~~~~~~
specialg.cpp:136:19: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             fscanf(fin, "%d", &x);
             ~~~~~~^~~~~~~~~~~~~~~
specialg.cpp:141:19: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             fscanf(fin, "%d%d", &x, &y);
             ~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100