Submission #82513

#	Time	Username	Problem	Language	Result	Execution time	Memory
82513		mpanyavin	Special graph (IZhO13_specialg)	C++14	0 / 100	1075 ms	7288 KiB

specialg

#include<bits/stdc++.h>
using namespace std;

const int N = 1 << 17;
const int INF = 1e+9;
int n, a[100001];
int m, t, u, v, incycle, kk;
int td[100001];
vector<int> g[100001];
vector< pair<int, int> > q[100001];
vector< pair<int, int> > ans;
int us[100001];
int st1[2 * N], st2[2 * N], pos[100001];

int fcycle(int x) {
    if (us[x] == 1) return x;
    if (a[x] == 0) return x;
    us[x] = 1;
    return fcycle(a[x]);
}

int getmin(int T, int ll, int rr, int L, int R) {
    //cout << "getmin(" << T << ", " << ll << ", " << rr << ", " << L << ", " << R << ")" << endl;
    if (L > R) return INF;
    if (ll == L && rr == R) return st2[T];
    int mm = (ll + rr) / 2;
    return min(getmin(T*2, ll, mm, L, min(R,mm)), getmin(T*2+1, mm+1, rr, max(L,mm+1), R));
}
int getmin2(int T, int ll, int rr, int L, int R) {
    //cout << "getmin2(" << T << ", " << ll << ", " << rr << ", " << L << ", " << R << ")" << endl;
    if (L > R) return INF;
    if (ll == L && rr == R) return st1[T];
    int mm = (ll + rr) / 2;
    return min(getmin2(T*2, ll, mm, L, min(R,mm)), getmin2(T*2+1, mm+1, rr, max(L,mm+1), R));
}

void dfs(int x, int dep) {
    //for (int i = 0; i < dep; i++) cout << "\t";
    //cout << "looking for queries... " << q[x].size() << endl;
    for (int j = 0; j < q[x].size(); j++) {
        int r = q[x][j].first;
        int w = q[x][j].second;

        //for (int i = 0; i < dep; i++) cout << "\t";
        //cout << r << " is on ";

        int h = -1;
        if (us[r] == 1) {
            //cout << "path\n";
            int z = getmin(1, 0, N-1, pos[r], dep - 1);
            if (z < w) h = -1;
            else h = dep - 1 - pos[r];
        }
        if (us[r] == 2) {
            //cout << "loop\n";
            int z1 = getmin(1, 0, N-1, 0, dep - 1);

            //for (int i = 0; i < dep; i++) cout << "\t";
            //cout << "min on path = " << z1 << endl;

            //for (int i = 0; i < dep; i++) cout << "\t";
            //cout << "pos[" << incycle << "] = " << pos[incycle] << endl;
            //for (int i = 0; i < dep; i++) cout << "\t";
            //cout << "pos[" << r << "] = " << pos[r] << endl;

            int z2;
            if (pos[incycle] <= pos[r])
                z2 = getmin2(1, 0, N-1, pos[incycle], pos[r] - 1);
            else
                z2 = min(getmin2(1, 0, N-1, pos[incycle], kk - 1),
                        getmin2(1, 0, N-1, 0, pos[r] - 1));
            if (min(z1, z2) < w) h = -1;
            else {
                h = dep;
                if (pos[incycle] <= pos[r])
                    h += pos[r] - pos[incycle];
                else
                    h += pos[r] + (kk - pos[incycle]);
            }
        }
        //for (int i = 0; i < dep; i++) cout << "\t";
        //cout << "distance to " << r << " at moment " << w << " = " << h << endl;
        ans.push_back({w, h});
    }
    for (int i = 0; i < g[x].size(); i++) {
        int to = g[x][i];

        //for (int i = 0; i < dep; i++) cout << "\t";
        //cout << "to = " << to << endl;

        if (us[to] == 0) {
            //for (int i = 0; i < dep; i++) cout << "\t";
            //cout << "went to " << to << endl;
            pos[to] = dep;
            us[to] = 1;
            st2[N + dep] = td[to];
            int p = (N + dep) / 2;
            while (p > 0) {
                st2[p] = min(st2[2 * p], st2[2 * p + 1]);
                p = p / 2;
            }

            dfs(to, dep + 1);

            pos[to] = 0;
            us[to] = 3;
            st2[N + dep] = INF;
            p = (N + dep) / 2;
            while (p > 0) {
                st2[p] = min(st2[2 * p], st2[2 * p + 1]);
                p = p / 2;
            }
        }
    }
}

int main() {
    //freopen("specialg.in", "r", stdin);
    //freopen("specialg.out", "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 0) a[i] = a[i];
        g[a[i]].push_back(i);
        td[i] = INF;
    }
    //for (int i = 1; i <= n; i++) {
        //cout << i << ": ";
        //for (int j = 0; j < g[i].size(); j++)
            //cout << g[i][j] << " ";
        //cout << endl;
    //}
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> t;
        if (t == 1) {
            cin >> u;
            td[u] = i;
        } else {
            cin >> u >> v;
            q[u].push_back({v, i});
        }
    }
    for (int i = 1; i <= n; i++) {
        if (us[i] == 0) {
            for (int ii = 0; ii < 2 * N; ii++) {
                st1[ii] = INF;
                st2[ii] = INF;
            }
            int st = fcycle(i);
            int c = i;
            while (c != st) {
                us[c] = 0;
                c = a[c];
            }
            int now = st;
            kk = 0;
            while (us[now] == 1) {
                us[now] = 2;
                st1[N + kk] = td[now];
                pos[now] = kk++;
                now = a[now];
            }
            for (int j = N - 1; j > 0; j--)
                st1[j] = min(st1[2 * j], st1[2 * j + 1]);

            //cout << "st = " << st << endl;
            //for (int j = 1; j <= n; j++) cout << us[j] << " "; cout << endl;
            //for (int j = 1; j < 2 * N; j++) cout << st1[j] << " "; cout << endl;

            now = st;
            do {
                incycle = now;
                dfs(now, 0);
                now = a[now];
            } while (now != st);
            c = st;
            int k = 0;
            while (a[c] != st) {
                us[c] = 3;
                st1[N + k] = INF;
                k++;
                c = a[c];
            }
            for (int j = N - 1; j > 0; j--)
                st1[j] = min(st1[2 * j], st1[2 * j + 1]);
        }
    }
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i].second << endl;
    return 0;
}

Compilation message (stderr)

specialg.cpp: In function 'void dfs(int, int)':
specialg.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < q[x].size(); j++) {
                     ~~^~~~~~~~~~~~~
specialg.cpp:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); i++) {
                     ~~^~~~~~~~~~~~~
specialg.cpp: In function 'int main()':
specialg.cpp:191:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ans.size(); i++)
                     ~~^~~~~~~~~~~~

• Subtask 1: 0 / 100