| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 47564 | fallingstar | 특수한 그래프 (IZhO13_specialg) | C++17 | 651 ms | 65536 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||