Submission #97205

#	Time	Username	Problem	Language	Result	Execution time	Memory
97205		Kastanda	Special graph (IZhO13_specialg)	C++11	100 / 100	502 ms	28504 KiB

specialg

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 100005;
int n, q, ts, M[N], P[N], C[N];
int Nxt[N], Dt[N], Len[N], OK[N], Lz[N];
set < pair < int , int > > Q[N], S[N];
vector < pair < int , int > > Cyc;
vector < int > TP;
void DFSC(int v)
{
    M[v] = ts;
    if (!Nxt[v] || M[Nxt[v]] && M[Nxt[v]] != ts)
        return ;
    if (M[Nxt[v]])
        Cyc.pb({Nxt[v], v});
    else
        P[Nxt[v]] = v, DFSC(Nxt[v]);
}
void DFS(int v)
{
    M[v] = 1;
    if (Nxt[v] && !C[Nxt[v]] && !M[Nxt[v]])
        DFS(Nxt[v]);
    TP.push_back(v);
}
inline void Push(int v)
{
    auto it = Q[v].lower_bound({v, -1});
    while (it != Q[v].end() && it->first == v)
    {
        OK[it->second] = 1;
        Len[it->second] += Lz[v];
        S[v].erase({it->second, it->first});
        it = Q[v].erase(it);
    }
    while (S[v].size() && S[v].rbegin()->first > Dt[v])
    {
        Q[v].erase({S[v].rbegin()->second, S[v].rbegin()->first});
        S[v].erase(*S[v].rbegin());
    }
    int nxt = Nxt[v];
    if (S[v].size() > S[nxt].size())
    {
        S[nxt].swap(S[v]);
        Q[nxt].swap(Q[v]);
        Lz[v] ++; Lz[nxt] --;
        swap(Lz[v], Lz[nxt]);
    }

    for (auto X : S[v])
    {
        S[nxt].insert(X);
        Len[X.first] += 1 + Lz[v] - Lz[nxt];
    }
    for (auto X : Q[v])
        Q[nxt].insert(X);
    S[v].clear();
    Q[v].clear();
    Lz[v] = 0;
}
void FNL(int v)
{
    M[v] ++;
    Push(v);
    if (M[Nxt[v]] < 2)
        FNL(Nxt[v]);
}
int main()
{
    scanf("%d", &n);
    memset(Dt, 63, sizeof(Dt));
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &Nxt[i]);
        if (Nxt[i] == i) Nxt[i] = 0;
        if (!Nxt[i]) Dt[i] = 0;
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
        int tp, v, u;
        scanf("%d%d", &tp, &v);
        if (tp == 1)
            Dt[v] = i, OK[i] = -1;
        else
        {
            scanf("%d", &u);
            S[v].insert({i, u});
            Q[v].insert({u, i});
        }
    }

    for (int i = 1; i <= n; i++)
        if (!M[i])
            ts ++, DFSC(i);
    ts = 0;
    for (auto X : Cyc)
    {
        ++ ts;
        int v = X.first, u = X.second;
        while (u != v)
            C[u] = ts, u = P[u];
        C[v] = ts;
    }
    memset(M, 0, sizeof(M));
    for (int i = 1; i <= n; i++)
        if (!M[i]) DFS(i);
    reverse(TP.begin(), TP.end());
    for (int v : TP)
        Push(v);
    memset(M, 0, sizeof(M));
    for (int i = 1; i <= n; i++)
        if (C[i] && !M[i]) FNL(i);
    for (int i = 1; i <= q; i++)
    {
        if (OK[i] == 0)
            printf("-1\n");
        if (OK[i] == 1)
            printf("%d\n", Len[i]);
    }
    return 0;
}

Compilation message (stderr)

specialg.cpp: In function 'void DFSC(int)':
specialg.cpp:13:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (!Nxt[v] || M[Nxt[v]] && M[Nxt[v]] != ts)
                    ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
specialg.cpp: In function 'int main()':
specialg.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
specialg.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &Nxt[i]);
         ~~~~~^~~~~~~~~~~~~~~
specialg.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
specialg.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &tp, &v);
         ~~~~~^~~~~~~~~~~~~~~~~
specialg.cpp:88:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &u);
             ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100