Submission #47564

#	Time	Username	Problem	Language	Result	Execution time	Memory
47564		fallingstar	Special graph (IZhO13_specialg)	C++17	0 / 100	651 ms	65536 KiB

specialg

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
 
using namespace std;
 
struct TQuery {int x, y, tme;};
 
const int N = 1e5+2;
const int LN = 17;
const int INF = 1e9;
 
int n, q, ncyc, nextv[N], exp[N], tme, num[N], low[N], p[LN][N], f[LN][N], cycid[N], cycpos[N], h[N], din[N];
vector<int> g[N], scc[N];
stack<int> st;
TQuery r[N];
 
class TTree
{
    vector<int> it;
public:
    void Update(int id, int sl, int sr, int u, int v)
    {
        if (sl == sr) 
        {
            it[id] = v;
            return;
        }
        int mid = (sl + sr) / 2;
        if (u <= mid) Update(id*2+1, sl, mid, u, v);
        else Update(id*2+2, mid+1, sr, u, v);
        it[id] = min(it[id*2+1], it[id*2+2]);
    }
    int Query(int id, int sl, int sr, int ql, int qr)
    {
        if (sl > qr || sr < ql || ql > qr) return INF;
        if (ql <= sl && sr <= qr) return it[id];
        int mid = (sl + sr) / 2;
        return min(Query(id*2+1, sl, mid, ql, qr), Query(id*2+2, mid+1, sr, ql, qr));
    }
    void Init(int n) {it = vector<int>(n << 2, INF);}
} tree[N];
 
void Dfs1(int u)
{
    num[u] = low[u] = ++tme;
    st.push(u);
    if (nextv[u])
    {
        int v = nextv[u];
        if (!num[v]) Dfs1(v), low[u] = min(low[u], low[v]);
        else low[u] = min(low[u], num[v]);
    }
    if (low[u] == num[u])
    {
        ++ncyc;
        int x; 
        do
        {
            x = st.top(); st.pop();
            scc[ncyc].push_back(x);
            low[x] = num[x] = INF;
        } while (x != u);        
        for (size_t i = 0; i < scc[ncyc].size(); ++i)
        {
            int v = scc[ncyc][i];
            cycid[v] = ncyc;
            cycpos[v] = i;
        }
        if (scc[ncyc].size() > 1U)
        {
            int n = scc[ncyc].size();
            tree[ncyc].Init(n);
            for (int i = 0; i < n; ++i)
            {
                int v = scc[ncyc][i];
                tree[ncyc].Update(0, 0, n-1, i, exp[v]);
            }
        }
        else f[0][ncyc] = exp[u];
    }
}
 
void Dfs2(int u)
{
    num[u] = 1;
    for (int v: g[u])
    {
        h[v] = h[u] + 1;
        p[0][v] = u;
        Dfs2(v);
    }
}
 
void BuildLCA()
{
    for (int j = 1; j < LN; ++j)
        for (int i = 1; i <= ncyc; ++i)
        {
            p[j][i] = p[j-1][p[j-1][i]];
            f[j][i] = min(f[j-1][i], f[j-1][p[j-1][i]]);
        }
}
 
int KthParent(int u, int k, int tme)
{
    int low = INF;
    for (int i = LN-1; i >= 0; --i)
        if (k - (1 << i) >= 0)
        {
            low = min(low, f[i][u]);
            u = p[i][u];
            k -= 1 << i;
        }
    if (low < tme) return -1;
    return u;
}
 
int QueryCycle(int cyc, int x, int y, int tme)       // x -> y
{
    int n = scc[cyc].size();
    if (x < y)
    {
        return min(tree[cyc].Query(0, 0, n-1, 0, x), tree[cyc].Query(0, 0, n-1, y+1, n-1)) > tme ? n - (y - x) : -1;
    }
    else return tree[cyc].Query(0, 0, n-1, y+1, x) > tme ? x - y : -1;
}
 
int Query(int x, int y, int tme)      // x -> y
{
    if (x == y) return 0;
    if (cycid[x] == cycid[y])
    {
        int cyc = cycid[x];
        x = cycpos[x], y = cycpos[y];
        return QueryCycle(cyc, x, y, tme);
    }
    else                                // x and y do not belong to the same cycle
    {
        int u = cycid[x], v = cycid[y];
        if (h[v] > h[u]) return -1;
        int re = h[u] - h[v];
        if (KthParent(u, h[u] - h[v], tme) != v) return -1;
        if (scc[v].size() > 1)            // v is a cycle
        {
            int val = QueryCycle(v, cycpos[nextv[scc[KthParent(u, h[u] - h[v] - 1, tme)][0]]], cycpos[y], tme);
            return val == -1 ? -1 : re + val;
        }
        else return re;
    }
}
 
void Solve()
{
    for (int i = 1; i <= n; ++i) 
        if (!num[i]) Dfs1(i);
    for (int i = 1; i <= n; ++i)
        if (nextv[i] && cycid[nextv[i]] != cycid[i]) 
        {
            g[cycid[nextv[i]]].push_back(cycid[i]);
            ++din[cycid[i]];
        }
    fill(num+1, num+1+ncyc, 0);
    for (int i = 1; i <= ncyc; ++i)
        if (!din[i] && !num[i]) Dfs2(i);               // start of chains
    for (int i = 1; i <= ncyc; ++i)
        if (!num[i]) Dfs2(i);                         // only cycles left
    BuildLCA();
    
    for (int i = 0; i < q; ++i)
    {
        int x = r[i].x, y = r[i].y, tme = r[i].tme;
        printf("%d\n",Query(x, y, tme));
    }
}
 
int main()
{
    scanf("%d",&n);
    for (int i = 1; i <= n; ++i) scanf("%d",&nextv[i]);
    int queries;
    scanf("%d",&queries);
    fill(exp+1, exp+1+n, INF);
    for (int i = 1, type, x, y; i <= queries; ++i)
    {
        scanf("%d",&type);
        if (type == 1)
        {
            scanf("%d",&x); exp[x] = i;
        }
        else
        {
            scanf("%d%d",&x,&y);
            r[q++] = {x, y, i};
        }
    }
    Solve();
    return 0;
}

Compilation message (stderr)

specialg.cpp: In function 'int main()':
specialg.cpp:180:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
specialg.cpp:181:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; ++i) scanf("%d",&nextv[i]);
                                  ~~~~~^~~~~~~~~~~~~~~~
specialg.cpp:183:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&queries);
     ~~~~~^~~~~~~~~~~~~~~
specialg.cpp:187:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&type);
         ~~~~~^~~~~~~~~~~~
specialg.cpp:190:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&x); exp[x] = i;
             ~~~~~^~~~~~~~~
specialg.cpp:194:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&x,&y);
             ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 100